题目详情

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],

输出: 6

解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

链接：

题解

动态规划：f(i)=max(f(i-1)+num[i],num[i]))

class Solution {public:    int maxSubArray(vector
    
     & nums) {        //dp        //f(i)表示下标为i的最大子序和        //更新方程：f(i)=max(f(i-1)+num[i],num[i])) 要么加上下一个要么重新从i开始计和        if(nums.empty())            return 0;        int numSize=nums.size();        int maxx=nums[0];        int maxx_global=nums[0];        for(int i=1;i
    

或者直接在线处理：

class Solution {public:    int maxSubArray(vector
    
     & nums) {        //在线处理        //策略：如果前面的和是有增益效果的（sum>0），则可以继续；如果前面的和无增益效果的（sum<0），则舍弃；maxx始终保持全局最大。        if(nums.empty())            return 0;        int sum=nums[0];        int maxx=sum;        for(int i=1;i
     
      0)                sum+=nums[i];            else                sum=nums[i];            maxx=max(maxx,sum);        }        return maxx;    }};