聖地亞歌

Leetcode P0053"Maximum Subarray" 题解

2020/08/25 Leetcode

博文中会简要介绍Leetcode P0053题目分析及解题思路。

“Maximum Subarray”是一道很有意思的动态规划问题，核心思路是动态规划，而递推表达式比较巧妙。

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

核心思路是动态规划，那么我们就需要知道最优子结构是什么，并且递推表达式是什么。

    令i是nums的下标，则该题最优子结构是，以nums[i]为结尾的连续的数组的和，而通过每次比较这个和，我们最终可以得到最大的和，即max

    递推表达式则是：
    sum = nums[i], if sum+nums[i] < nums[i]
    这个情况代表的就是sum是个负数而nums[i]是个正数，此时下一次sum的计算以nums[i]为开头比前面的sum要更大，所以舍弃前面计算的sum

    sum += nums[itr]
    即sum在持续增大
Plaintext

根据上述的递推表达式和最优子结构，我们就可以得到最终的最大连续子数组的和。

以下是Java的题解代码实现。

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        
        int itr = 1, sum = nums[0], maxSum = nums[0];
        while (itr < nums.length) {
            if (nums[itr] > sum+nums[itr]) {
                sum = nums[itr];
            }
            else {
                sum += nums[itr];
            }
            
            maxSum = Math.max(maxSum, sum);
            ++itr;
        }
        
        return maxSum;
    }
}
Java

以下是C++的题解代码实现。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.size() == 0)
            return 0;
        
        int itr = 1, sum = nums[0], max_sum = nums[0];
        while (itr < nums.size()) {
            if (sum+nums[itr] < nums[itr]) {
                sum = nums[itr];
            }
            else
                sum += nums[itr];
            
            ++itr;
            max_sum = max(max_sum, sum);
        }
        
        return max_sum;
    }
};
C++

Search