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

2021-06-01 02:05

阅读：526

标签：amp code loading 技术 img 最大子数组 rank base 连续

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

题目：

技术图片

思路：

dp数组的定义：dp[i]是以 nums[i] 结尾的最大子数组和。
base_case：dp[0] = nums[0]
状态转移方程:dp[i]有两种「选择」，要么与前面的相邻子数组连接，形成一个和更大的子数组；要么不与前面的子数组连接，自成一派，自己作为一个子数组。

dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);

代码：

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

        dp[0] = nums[0];

        for(int i = 1; i

Rank：

技术图片

Tips：

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

标签：amp code loading 技术 img 最大子数组 rank base 连续

原文地址：https://www.cnblogs.com/lzyrookie/p/14727060.html

上一篇：python程序设计基础

下一篇：nodejs

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：动态规划——剑指 Offer 42. 连续子数组的最大和
文章链接：http://soscw.com/essay/89867.html

亲，登录后才可以留言！

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

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

题目：

思路：

代码：

Rank：

Tips：

评论

热门文章

推荐文章

最新文章

置顶文章