首页 🍒LeetCode,🐶算法

题目

IMbbD5iCVM.png

思路

此题乍一看是用滑动窗口,但是因为有负数所以滑动窗口不能解决这个题。

采用动态规划就要求出状态转移方程,定义数组dp,dp[i]表示以nums[i]结尾的最长连续子数组和。

那么,知道dp[0..i -1]的值,如果求出dp[i]:
因为数组中有负数所以dp[i]有两种选择,要么加入前面的数组,要么自成一派自己作为新的数组。
dp[i] = max(nums[i], nums[i] + dp[i - 1]);
dp的状态转移方程确定就可以写出这道题了。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp = vector<int>(nums.size(), 0);
        dp[0] = nums[0];
        int res = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            dp[i] = max(nums[i], nums[i] + dp[i - 1]);
            res = max(res, dp[i]);
        }
        return res;
    }
};



文章评论