# 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 =  * len(nums)

DP = nums
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
max_sum = nums

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.

Posted on Categories Leetcode