【LeetCode热题100】【数组】最大子数组和

叶茂林

发布于 2024-04-02 08:24:31

1090

发布于 2024-04-02 08:24:31

只要和的值不要哪个子数组，原问题的解由子问题的解组成，可以用动态规划，数组中每个元素都是一个子数组的结尾，dp[i]是以num[i]为结尾的最大子数组和，dp[i]要么是前一个子数组和加上当前元素，要么就是当前元素新开一个子数组，取决于这两个值哪个大

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-04-01，如有侵权请联系 cloudcommunity@tencent.com 删除

数组