LeetCode 53 Maximum Subarray

概述

https://leetcode.com/problems/maximum-subarray/

动态规划法

极值问题，直接上动态规划。

dp[i] 表示以 nums[i] 开头的连续数组的最大和。

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

Links: leetcode-53-maximum-subarray

未经允许，禁止转载，本文源站链接：https://iamazing.cn/