动态规划——剑指 Offer 42. 连续子数组的最大和

动态规划——剑指 Offer 42. 连续子数组的最大和

题目:

动态规划——剑指 Offer 42. 连续子数组的最大和

思路:

  1. dp数组的定义:dp[i]是以 nums[i] 结尾的最大子数组和。
  2. base_case:dp[0] = nums[0]
  3. 状态转移方程:dp[i]有两种「选择」,要么与前面的相邻子数组连接,形成一个和更大的子数组;要么不与前面的子数组连接,自成一派,自己作为一个子数组。
dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);

代码:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int min = INT_MIN;
        vector<int> dp(n+1, INT_MIN);

        dp[0] = nums[0];

        for(int i = 1; i<n;i++){
            dp[i] = max(nums[i], nums[i] + dp[i-1]);
        }

        return *max_element(dp.begin(),dp.end());

    }
};

Rank:

动态规划——剑指 Offer 42. 连续子数组的最大和

Tips:

上一篇:42. 接雨水


下一篇:算法 (桶排序)