19. 剑指 Offer 42. 连续子数组的最大和

要求

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。

思路

动态规划：

• 状态定义： 设动态规划列表 dp ，dp[i] 代表以元素 nums[i] 为结尾的连续子数组最大和。

• 转移方程： 若 dp[i-1]≤0 ，说明 dp[i - 1] 对 dp[i] 产生负贡献，即 dp[i-1] + nums[i] 还不如 nums[i]本身大。若dp[i-1]＞0，说明 dp[i - 1] 对 dp[i] 产生正贡献。

• 初始状态： dp[0] = nums[0]，即以 nums[0] 结尾的连续子数组最大和为 nums[0]。

• 返回值： 返回 dp 列表中的最大值，代表全局最大值

解题

#include <iostream>
using namespace std;
#include <vector>

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size(), 0);
        int max = nums[0];  // 初始化最大子数组和，为数组第一个元素
        dp[0] = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            if (dp[i - 1] <= 0)
                dp[i] = nums[i];    // dp[i - 1]小于等于0，对子数组和产生负贡献，所以不需要＋
            else
                dp[i] = dp[i - 1] + nums[i]; // dp[i - 1]大于0，对子数组和产生正贡献，所以需要＋
            if (dp[i] > max) 
                max = dp[i];
        }
        return max;
    }
};


void test01()
{
    Solution soulution;
    vector<int> nums;
    nums.push_back(-2);
    nums.push_back(1);
    nums.push_back(-3);
    nums.push_back(4);
    nums.push_back(-1);
    nums.push_back(2);
    nums.push_back(1);
    nums.push_back(-5);
    nums.push_back(4);

    cout << soulution.maxSubArray(nums) << endl;
}

int main()
{
    test01();

    system("pause");
    return 0;
}

希望本文对大家有帮助，上文若有不妥之处，欢迎指正

分享决定高度，学习拉开差距