LeetCode第53题 最大子数组和

大子数组和"/>

LeetCode第53题 最大子数组和

可恶，我明明想今天早点睡觉

第一反应

双指针，虽然不知道要用双指针干什么，但反正是双指针。（后面看了下好像不是双指针）
首先起点找一个正数（没有就找一个最大的非正数），
然后把所有相邻的正负数加起来，让剩下的变成一个正数一个负数依次排列。也可以排除两侧的负数。
然后，对每一个负数，看看它绝对值是不是比两侧的正数都要大，如果是的话就先不管，继续看其他的数；如果不是的话，就把这三个数加起来合并在一起
看完一轮再来一轮，重复直到无法减少数字，然后找到其中最大的正数
很合理，时间复杂度大概是O(n^2)
感觉算是简单题里比较难的了

不是，别，我感觉脸有点疼
额
首先，即使是分治法，至少也要O(n)的复杂度对吧，没排过序的数组至少要把所有数字看一遍，这就至少O(n)了。那我就搞个O(n)吧
等下，好像确实只要遍历一遍
用max保存最大值
一个变量current保存当前的累加值，遇到负数的时候，如果大于current就current归零，从下一个正数开始记录current；如果负数小于current就直接加上这个负数，然后继续找。
合理，可以优化到O(n)

提交通过

class Solution {public int maxSubArray(int[] nums) {int max = -100000;int current = 0;int sumNeg = 0;for(int i = 0 , len = nums.length; i < len ; ){if(nums[i] < 0){sumNeg = 0;while(i < len &&  nums[i] < 0){if(nums[i] > max){max = nums[i];}sumNeg += nums[i];i++;}if(current + sumNeg > 0){current = current+sumNeg;}else{current = 0;}}else if(nums[i] > 0){current += nums[i];if(current > max){max = current;}i++;}else{if(nums[i] > max){max = nums[i];}i++;}// System.out.println("i = " + i + " ; current = " + current + " ; max = " + max);}return max;}
}

看看题解

感觉我的智商被完爆了
这个写法和我的思路是一样的（一样个锤子） ，但是实现起来太潇洒了

class Solution {public int maxSubArray(int[] nums) {int pre = 0;int ans = nums[0];//解决长度为1的情况for(int x : nums){pre = Math.max(pre+x, x);ans = Math.max(pre, ans);}return ans;}
}

看看题解的动态规划方法，原话是这样的

但是这个状态转移方程怎么看起来只找了下标从0开始的子数组呢？看题目名字好像改过，我怀疑这个题目改过。按照现在的题目，应该是求max{f(i,j)}，其中f(i,j)表示i到j-1的最大子数组之和0<=i<j<=n-1
f(i,j) = max{ nums[i] , nums[j] , f(i+1, j) + nums[i] , f(i,j-1) + nums[j-1] }

为什么能用上面那个简单的转移方程代替下面这个两个变量的转移方程我也不知道，再研究吧