Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],

the contiguous subarray [4,−1,2,1] has the largest sum = 6.

 

 

---

 

 

找出和最大的子串。

动态规划 ，维护一个变量previous，记录之前的最大值。

当前的最大值就是Math.max(previous + nums[i], nums[i])。

 

1 /** 2  * @param {number[]} nums 3  * @return {number} 4  */ 5 var maxSubArray = function(nums) { 6     if(nums.length === 0) return 0; 7     var previous = Math.max(0, nums[0]), max = nums[0]; 8     for(var i = 1; i < nums.length; i++){ 9         previous = Math.max(previous + nums[i], nums[i]);10         max = Math.max(previous, max);11     }12     return max;13 };

 

 

一开始写的比较啰嗦。

动态规划，到当前index的子串的最大值可能有三种情况：

1. 当前元素的，nums[i]

2. nums[i] + 包括了上一个元素nums[i - 1]的最大子串的和

3. nums[i] + 上一个元素nums[i - 1]之前的最大值(不包括nums[i - 1]) + nums[i - 1]

 

1 /** 2  * @param {number[]} nums 3  * @return {number} 4  */ 5 var maxSubArray = function(nums) { 6     if(nums.length === 0) return 0; 7     var dp = [], max = nums[0], previous, current; 8     dp[0] = {previous : 0, current: nums[0]}; 9     for(var i = 1; i < nums.length; i++){10         previous = dp[i - 1].current;11         current = Math.max(nums[i], nums[i] + dp[i - 1].current,12             nums[i] + nums[i - 1] + dp[i - 1].previous);13         dp[i] = {previous : previous, current: current};14         max = Math.max(current, max);15     }16     return max;17 };