leetcode hot100刷题日记——7.最大子数组和

class Solution {
public:int maxSubArray(vector<int>& nums) {//方法一：动态规划//dp[i]表示以i下标结尾的数组的最大子数组和//那么在i=0时，dp[0]=nums[0]//之后要考虑的就是我们要不要把下一个数加进来，如果下一个数加进来会使结果变大那就加进来//但要是下一个数加进来之后，还不如这个数单独大，那我们就舍弃前面的子数组和，直接用单独这个数，即：//dp[i]=max(dp[i-1]+nums[i],nums[i])//什么情况下“下一个数加进来之后，还不如这个数单独大”？//dp[i-1]为负数的时候// int n=nums.size();// vector<int>dp(n);// dp[0]=nums[0];// int maxx=nums[0];// for(int i=1;i<n;i++){//     dp[i]=max(dp[i-1],0)+nums[i];//     maxx=max(dp[i],maxx);// }// return maxx;//方法2：前缀和+贪心//最大子数组和=max(所有当前前缀和-最小前缀和)//为什么只需要维护最小前缀和呢？//因为最大子数组和这个问题要看的是连续部分！//你如果求最大前缀和-最小前缀和//那么有可能最大前缀和比最小前缀和短！//eg. 5 4 3 -2 -1 -5//最大前缀和是5+4+3=12//最小前缀和是5+4+3-2-1-5=4//最大前缀和-最小前缀和=8//但是不对啊！实际上最大子数组和是5+4+3=12啊！//所以最小前缀和初始化值为0int n=nums.size();if(n==1)return nums[0];int ans=INT_MIN;int minn=0;int sum=0;for(int i=0;i<n;i++){sum+=nums[i];ans=max(ans,sum-minn);minn=min(minn,sum);}return ans;}
};

时间复杂度：O(N)
空间复杂度：
方法一是O(N)
方法二是O(1)