Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input:[-2,1,-3,4,-1,2,1,-5,4],
Output:6
Explanation:[4,-1,2,1] has the largest sum = 6.
Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
寻找和最大的子串，子串必须是连续的，若将数组中每个数累加，则时间复杂度为0(n^2)，题目还要求用分治法Divide and Conquer Approach来解，这个分治法的思想就类似于二分搜索法，从数组中间开始，分别向左向右进行累加，得到最大的累加和，然后再与左边、右边最大的累加和比较，得出最大累加和，时间复杂度为O(nlogn)。
注意点：
为减少空间复杂度，函数传参使用实参而不用形参。
代码:
int max(int n,int m)
{
return n>m?n:m;
}
int getmax(vector<int>&nums,int left,int right) //使用实参(&),而不用形参
{
if(left>=right)
return nums[left];
int mid = (left+right)/2;
int leftMax=getmax(nums, left, mid-1);
int rightMax=getmax(nums, mid+1, right);
int midMax=nums[mid];
int t=midMax;
for(int i=mid-1;i>=left;i--)
{
t+=nums[i];
midMax=max(midMax,t);
}
t=midMax;
for(int i=mid+1;i<=right;i++)
{
t+=nums[i];
midMax=max(midMax,t);
}
return max(midMax,max(leftMax,rightMax));
}
int maxSubArray(vector<int>& nums) {
if(nums.empty())
return 0;
return getmax(nums,0,nums.size()-1);
}
网上还有两种方法：
https://www.cnblogs.com/bugfly/p/3922390.html
动态规划，假设start[i]为a[i],a[i+1]...a[n-1]数组中以a[i]开头的最大字段和，all[i]为a[i],a[i+1]...a[n-1]数组的最大字段和，则有
start[i] = max{a[i], start[i+1]+a[i]}
all[i] = max{start[i], all[i+1]}
此时时间复杂度为O(n)，空间复杂度也为O(n)，不过空间可以优化为O(1)，为便于理解，不作优化处理了，代码如下：
1 class Solution {
2 public:
3 int maxSubArray(int A[], int n) {
4 int start[n]; //start[i]为a[i],a[i+1]...a[n-1]数组中以a[i]开头的最大字段和
5 int all[n]; //all[i]为a[i],a[i+1]...a[n-1]数组的最大字段和
6 memset(start, 0, sizeof(start));
7 memset(all, 0, sizeof(all));
8 start[n-1] = all[n-1] = A[n-1]; //初始化
9 for(int i=n-2; i>=0; --i) {
10 start[i] = max(A[i], start[i+1]+A[i]);
11 all[i] = max(start[i], all[i+1]);
12 }
13 return all[0];
14 }
15 };
还有一种Kadane算法，相当巧妙，时间复杂度亦为O(n)，空间复杂度为O(1)，具体请问度娘，代码如下：
1 class Solution {
2 public:
3 int maxSubArray(int A[], int n) {
4 int ans = -0x3fffffff; //预处理最小值
5 int sum = 0;
6 for(int i=0; i<n; ++i) {
7 sum += A[i]; //每次计算连续元素
8 ans = max(ans, sum); //判断ans是否又变大了
9 if( sum < 0 ) sum = 0; //如果sum第一次小于0，立即更新，子数组重新开始
10 }
11 return ans;
12 }
13 };
网友评论