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.