Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Maximum Subarray

Leetcode algorithms 第 53 题:Maximum Subarray。

题目

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

解答

最大连续子序列和,使用动态规划解决。令dp[i]表示以i结束的最大连续子序列和,则求dp[i]时,可以考虑dp[i-1]:

  • 如果dp[i-1] > 0,则把以i-1结尾的最大连续子序列再加上i本身,可以得到以i结尾的最大连续子序列和,即dp[i] = dp[i-1] + a[i]
  • 否则,即dp[i-1] <= 0,则把i自己当做一个连续子序列时会是一个最大的,因为其前面的和是负数,即dp[i] = a[i]

最终的答案为所有的dp[i]中最大的一个。

另外,由于dp[i]仅依赖于前一个dp[i-1],所以可以只使用一个变量cur取代整个dp数组,优化空间复杂度。

具体代码如下:

class Solution {
public:
    int maxSubArray(int A[], int n) {
        if (n <= 0) return 0; //长度不足
        
        int ans = A[0], cur = A[0]; //答案,dp值
        for (int i = 1; i < n; i++)
            cur = cur > 0 ? cur + A[i] : A[i], ans = max(ans, cur);
            
        return ans;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论