求数组中元素相加所能取得的最大值, 这些元素必须相临, 复杂度为 O(n)
- Example
- Input: [-2,1,-3,4,-1,2,1,-5,4],
- Output: 6
- Explanation: [4,-1,2,1] has the largest sum = 6.
解法
- var maxSubArray = function(nums) {
- let max = nums[0];
- let sum = 0;
- const len = nums.length;
- for(let i=0; i <len; i++){
- // 遍历累加
- sum += nums[i]
- // 累加一次就和以前的最大值比较, 并将最大值赋予给 max, 这样 max 永远都是最大值
- if(sum> max){
- max = sum
- }
- // 最关键的一步, 当 sum 累加的值为负数, 与下一个数累相加和只会变小
- // 所以这个时候, 让 sum=0, 从下一个数开始从新累加, 然后新累加的值, 继续和原来最大的 max 比较
- if( sum <0){
- sum = 0;
- }
- }
- return max
- };
思考如果返回的是最大和的元素组成
- var arr = [0,-3,-1,-23,9,99,-5,-5]
- var res = maxSubArray(arr)
- console.log(res) // [9,99]
解法:
- var maxSubArray = function(nums) {
- let max = nums[0];
- let sum = 0;
- const len = nums.length;
- let start = 0;
- let end = 0;
- let e = 0;
- let s = 0;
- for(let i=0; i < len; i++){
- sum += nums[i]
- if(sum>= max){
- // 只要出现 sum 大于 max, 那么最后一个值肯定就是 sum[i]
- end = i + 1
- start = s
- max = sum
- }
- if( sum < 0){
- sum = 0;
- // 当 sum 为负数, 有可能接下来的累加值会大于之前的最大 max
- // 所以这里的起点先保存一个, 后面如果累加大于前面的, 起点从这里算
- // [1,2,-4,5,6] 为例子: 当 i 为 2 的时候, sum = 1+2-4 =-1 小于 0
- // 而接下来 5+6 会是最大值, 起点是 5 所在的位置为 i=3
- s = i + 1
- }
- }
- const arr = nums.slice(start,end )
- return arr
- };
来源: http://www.jianshu.com/p/1dfcd6acdd78