53. 最大子数组和

Problem: 53. 最大子数组和-最大子序和

思路

392.判断子序列
1143.最长公共子序列
1035.不相交的线
674.最长连续递增序列
718.最长重复子数组**超时

这几道题目都有相同之处,都是求某个特殊的子序列,例如本道题目是求最大的子序列,本道题目的子序列要求是连续序列。

dp数组含义:

dp[i]表示[0...i]的最大子序列和

初始化:

[0...0]的最大子序列和是他本身dp[0]=nums[0]

递推公式:

要求最大的连续子序列,那么如果当前数比之前的连续最大子序列和还要大,那么肯定要舍弃之前的,之后数的加自己肯定要比之前要大,dp[i]=max(之前最大序列+当前数,当前数)

Code

[]

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        //dp[i] 表示[0...i]的最大子序列和
        vector<int> dp(nums.size());
        //初始化dp[0]=nums[0];
        dp[0]=nums[0];
        int res=dp[0];
        //递推公式 dp[i]=max(自己,之前的最大子序列+自己)
        for(int i=1;i<nums.size();i++) {
            dp[i]=max(nums[i],dp[i-1]+nums[i]);
            res=max(res,dp[i]);
        }
        for(int i=0;i<nums.size();i++)
            cout << dp[i] << endl;
        return res;
    }
};