Leetcode Maximum Subarray.pdf

文档介绍：靖空间
效苏秦,闭关修炼! 吾破关之日,就是中国横添一颗计算机星级人才之
日!
Leetcode Maximum Subarray
分类: Algorithm算法 2013-12-19 08:06 124人阅读评论(0) 收藏举报
LeetcodeMaximum Subarray
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.
click to show more practice.
More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach,
which is more subtle.
这是个很经典的题目了。
两个方法:
1 动态规划法
2 二分法
这里是使用简单的动态规划法,只需要一个额外空间记录就可以了,只要知道方法,实现起来比二分法简单多了。
class Solution {
public:
int maxSubArray(int A[], int n) {
int tempSum = 0;
int maxSum = INT_MIN;
for (int i = 0; i < n; i++)
{
tempSum += A[i];
maxSum = max(tempSum, maxSum);
if (tempSum < 0) tempSum = 0;
}
return maxSum;
}
};
二分法关键: 当最大子序列出现在中间的时候,应该如何计算最大值?
1 要循环完左边和右边的序列
2 从中间到左边,找到最大值
3 从中间到右边,找到最大值
这个判断条件还是有点难想的。
不过本题卡我时间最长的居然是一个小问题:!
1
class Solution {
public:
int maxSubArray(int A[], int n) {
if (n < 1) return 0;
if (n == 1) return A[0];
return biSubArray(A, 0, n-1);
}
//low和up均为C++存储内容的下标
int biSubArray(int A[], int low, int up)
{
if (low > up) return INT_MIN;
if (low == up) return A[low];
int mid = low+((up-low)>>1);
//low不小心写成了0,结果浪费了很长时间debug