最大连续子段和问题（动态规划/贪心）

最大连续子段和问题

传送门

问题描述

给定一个数组，记录一串数字，且元素值即存在正数也存在负数，现在要你求出数组中最大的连续子段和

分析

动态规划解法

这是一个经典的线性dp的模型。

状态表示

$f(i) ： $ 表示以a[i] 为结尾的最大子序列的和的值

状态计算

对于当前位置 i 有两种情况：

• 加入当前子序列‘(f(i) = f(i - 1) + a[i])
• 不加入当前子序列(f(i) = a[i])

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

贪心解法

贪心问题首先定义贪心策略：

如果对于当前元素值前一段最大子序和 < 0 那么我们就放弃前一段，否则则加上a[i]。

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