博文中会简要介绍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在持续增大
根据上述的递推表达式和最优子结构，我们就可以得到最终的最大连续子数组的和。
以下是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;
}
}
以下是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;
}
};