数据结构学习 jz42连续子数组最大和

关键词：动态规划?滚动数组 最长上升子序列

这道题比较简单，类似最长上升子序列，比最长上升子序列简单。

和最长上升子序列的区别：这道题因为是连续的，所以只用记录max就好了。最长上升子序列是不连续的，所以需要记录一整个数组。

题目：

思路：

dp状态：

dp[i] ：i算进最高销售额，i作为区间右值 ( ,i] 时的最高销售额

转移方程：

dp[i]=max(dp[i-1]+sales[i],sales[i])

复杂度计算：

时间复杂度O(n)

空间复杂度O(1) 滚动数组优化

代码：

class Solution {
public:

    int maxSales(vector<int>& sales) {
        if(sales.size()==1) return sales[0];
        int dp=sales[0];
        int max=dp;
        for(int i=1;i<sales.size();++i)
        {//状态：i算进最高销售额，i作为区间右值 ( ,i] 时的最高销售额
            if(sales[i]<sales[i]+dp)
                dp+=sales[i];//如果接上前面之后，销售额变高了，说明要接上
            else
                dp=sales[i];//如果接上前面之后，销售额变低了，说明不用接上
            max=std::max(dp,max);
        }
        return max;
    }
};