# 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.