subarray and subsequence

Maximum subarray

DP solution. We know the maximum sum with subarray ending at i will either come from itself(nums[i]) or the previous subarray sub + nums[i]. We find all the max sum of subarray ending at all possible position, then take the max of it.

    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        DP = [0] * len(nums)

        DP[0] = nums[0]
        for i in range(1, len(DP)):
            DP[i] = max(DP[i - 1] + nums[i], nums[i])

        return max(DP)

Can also reduce the space down to O(1) by keeping the max sub array and updating it for every subarray ending at i.

        prev_sum = nums[0]
        max_sum = nums[0]

        for i in range(1, len(nums)):
            cur_sum = max(prev_sum + nums[i], nums[i])
            max_sum = max(cur_sum, max_sum)
            prev_sum = cur_sum

        return max_sum

349Intersection of two array

Given two arrays, write a function to compute their intersection First, we iter through the first list and put all its elements into a dictionary d with value 0. Then we iter through the other list and if the char is in the dict, make that char’s value 1, else pass. Iter through the dict and store the char with value 1 in the result.

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax