LeetCode 53 Maximum Subarray

Tag: 动态规划问题 LeetCode Posted on 2022-02-16 13:50:10 Edited on 2022-02-16 14:46:31 Views: 163

概述

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;
    }
};

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