本文主要是介绍[LeetCode]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.
click to show 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.
【分析】
详细参考：编程之美之2.14 求数组的子数组之和的最大值
【代码】
/*********************************
* 日期：2015-01-27
* 作者：SJF0115
* 题目: 53.Maximum Subarray
* 网址：https://oj.leetcode.com/problems/maximum-subarray/
* 结果：AC
* 来源：LeetCode
* 博客：
**********************************/
#include <iostream>
#include <climits>
using namespace std;class Solution {
public:int maxSubArray(int A[], int n) {if(n <= 0){return 0;}//if// 最大和int max = A[0];// 当前最大和int cur = 0;for(int i = 0;i < n;++i){// 一旦当前最大和小于0就重置为0,一个负数只能使最大和变小if(cur < 0){cur = 0;}//ifcur += A[i];if(cur > max){max = cur;}//if}//forreturn max;}
};
int main(){Solution solution;int n = 9;int A[] = {-2,1,-3,4,-1,2,1,-5,4};int result = solution.maxSubArray(A,n);// 输出cout<<result<<endl;return 0;
}
【分析二】
如果将所给数组(A[0],...,A[n-1])分为长度相等的两段数组(A[0],...,A[n/2-1])和(A[n/2],...,A[n-1]),分别求出这两段数组各自最大子段和，
则原数组(A[0],...,A[n-1])的最大子段和分为以下三种情况，要么在前半部分a中，要么在后半部分b中，要么跨越a和b之间的边界：
a.(A[0],...,A[n-1])的最大子段和与(A[0],...,A[n/2-1])的最大子段和相同；
b.(A[0],...,A[n-1])的最大子段和与(A[n/2],...,A[n-1])的最大子段和相同；
c.(A[0],...,A[n-1])的最大子段跨过其中间两个元素A[n/2-1]到A[n/2]；
对应a和b两个问题是规模减半的两个相同的子问题，可以用递归求得。
对于c,需要找到以A[n/2-1]结尾的最大的一段连续数组之和S1=(A[i],...,A[n/2-1])和以A[n/2]开始的最大的一段连续数组之和S2=(A[n/2],...,A[j]),那么第三种情况的最大值为S1+S2。
只需要对原数组进行一次遍历即可。在a中的部分是a中包含右边界的最大子数组，在b中的部分是b中包含左边界的最大子数组。
这其实是一种分治策略，时间复杂度为O（nlogn）。
【代码二】
/********************************** 日期：2015-02-03* 作者：SJF0115* 题目: 53.Maximum Subarray* 网址：https://oj.leetcode.com/problems/maximum-subarray/* 结果：AC* 来源：LeetCode* 博客：**********************************/#include <iostream>#include <climits>using namespace std;class Solution {public:int maxSubArray(int A[], int n) {return Divide(A,0,n-1);}private:int Divide(int A[],int left,int right){if(left > right){return 0;}//ifif(left == right){return A[left];}//if//int mid = left + (right - left) / 2;//1.跨越a和b之间的部分//1.1在a中的部分是a中包含右边界的最大子数组int sum = 0;int leftMax = A[mid];for(int i = mid;i >= left;--i){sum += A[i];leftMax = max(sum,leftMax);}//for//1.2在b中的部分是b中包含左边界的最大子数组sum = 0;int rightMax = A[mid+1];for(int i = mid+1;i <= right;++i){sum += A[i];rightMax = max(sum,rightMax);}//for// 前半部分最大和int aMax = Divide(A,left,mid);// 后半部分最大和int bMax = Divide(A,mid+1,right);// 跨越mid的最大和int cMax = leftMax + rightMax;return max(max(aMax,bMax),cMax);}};int main(){Solution solution;int n = 9;int A[] = {-2,1,-3,4,-1,2,1,-5,4};//int A[] = {-9,-2,-3,-5,-3};//int A[] = {0,-2,3,5,-1,2};int result = solution.maxSubArray(A,n);// 输出cout<<result<<endl;return 0;}
【分析三】
只遍历数组一遍，当从头到尾部遍历数组A， 遇到一个数有两种选择 （1）加入之前subArray （2）自己另起一个subArray
设状态S[i], 表示以A[i]结尾的最大连续子序列和，状态转移方程如下:
S[i] = max(S[i-1] + A[i],A[i])
时间复杂度：O(n) 空间复杂度：O(n)
【代码三】
/*--------------------------------------------* 日期：2015-02-03* 作者：SJF0115* 题目: 53.Maximum Subarray* 网址：https://oj.leetcode.com/problems/maximum-subarray/* 结果：AC* 来源：LeetCode* 博客：-----------------------------------------------*/class Solution {public:int maxSubArray(int A[], int n) {int S[n];int maxSum = A[0];S[0] = A[0];// 动态规划for(int i = 1;i < n;i++){S[i] = max(S[i-1] + A[i],A[i]);if(S[i] > maxSum){maxSum = S[i];}//if}//forreturn maxSum;}};
【解法四】
对前一个方法继续优化，从状态转移方程上S【i】只与S【i-1】有关，与其他都无关，因此可以用一个变量来记住前一个的最大连续数组和就可以了。
这样就可以节省空间了。
时间复杂度：O(n) 空间复杂度：O(1)
【代码四】
/*--------------------------------------------* 日期：2015-02-03* 作者：SJF0115* 题目: 53.Maximum Subarray* 网址：https://oj.leetcode.com/problems/maximum-subarray/* 结果：AC* 来源：LeetCode* 博客：-----------------------------------------------*/class Solution {public:int maxSubArray(int A[], int n) {int maxSum = A[0];// sum 记住前一个的最大连续数组和int sum = 0;// 动态规划for(int i = 0;i < n;i++){sum += A[i];sum = max(sum,A[i]);if(sum > maxSum){maxSum = sum;}//if}//forreturn maxSum;}};
这篇关于[LeetCode]53.Maximum Subarray的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
