Maximum Subarray
Given an integer array nums , find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. [#53]
Example: Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and
conquer approach, which is more subtle.
题意：给定整数数组nums，找到具有最大和的连续子数组，返回和值
此题还是能用子序列推导式解决：
>>> sub = lambda s:[s[i:j] for i in range(len(s)) for j in range(i+1,len(s)+1)] >>> arr = [-2,1,-3,4,-1,2,1,-5,4] >>> maxsum = max([sum(i) for i in sub(arr)]) >>> maxsum 6 >>> [i for i in sub(arr) if sum(i)==maxsum] [[4, -1, 2, 1]] >>>
Jump Game
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index. [#55]
Example 1: Input: [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index. Example 2: Input: [3,2,1,0,4] Output: false Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index.
