题解 | #连续子数组的最大和#

连续子数组的最大和

https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484

方法一:动态规划

1、创建一个数组dp,记录不同位置结尾的子数组和的最大值,有两种情况,其一,当前的元素单独作为一个子数组;其二,与前面的元素组成子数组,所以可以得到如下的状态转移方程:

dp[i] = max(array[i], array[i] + dp[i - 1]);

2、数组dp中的最大值即为连续子数组的最大和。

时间复杂度:o(n)

空间复杂度:o(n)

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int>& array) {
        // 特殊情况处理
        if (array.size() == 1)
            return array[0];
        // 记录不同位置结尾的子数组和的最大值
        vector<int> dp(array.size(), 0);
        dp[0] = array[0];
        int max_sum = INT_MIN;
        for (int i = 1; i < array.size(); i++) {
            dp[i] = max(array[i], array[i] + dp[i - 1]);
            if (dp[i] > max_sum)
                max_sum = dp[i];
        }

        return max_sum;
    }
};

上述方法,可以进一步优化空间复杂度,使用一个临时的int值来存储上一个位置的最大子数组和即可。

时间复杂度:o(n)

空间复杂度:o(1)

#include <climits>
class Solution {
  public:
    int FindGreatestSumOfSubArray(vector<int>& array) {
        // 特殊情况处理
        if (array.size() == 1)
            return array[0];

        int max_sum = INT_MIN;
	  	// 存储上一个位置作为结尾的最大子数组和
        int temp = array[0];
        for (int i = 1; i < array.size(); i++) {
            temp = max(array[i], array[i] + temp);
            if (temp > max_sum)
                max_sum = temp;
        }

        return max_sum;
    }
};

刷题题解(c++) 文章被收录于专栏

算法题题解(c++)

全部评论

相关推荐

点赞 评论 收藏
分享
06-25 09:33
厦门大学 Java
程序员饺子:现在日常估计没啥hc了,等到八月多估计就慢慢有了。双九✌🏻不用焦虑的
投递快手等公司10个岗位
点赞 评论 收藏
分享
05-27 14:57
西北大学 golang
强大的社畜在走神:27届真不用急,可以搞点项目、竞赛再沉淀沉淀,我大二的时候还在天天打游戏呢
投递华为等公司10个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务