@chawuciren
2018-12-10T16:29:48.000000Z
字数 1022
阅读 676
未分类
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.
第一个想法是,先算所有两个元素的,再算所有三个元素的。。。以此类推(O(n)?)
改进一下,反着来算,先算arraysize的,再算arraysize-1,嗯。。。假装这是DP。
要算arraysize的,就一定要先算arraysize-1(每次都有两种情况,这些统统记下来,最后比较大小)
返回最大值
这种方法可以画成一颗递归树,底层有2^n-1种可能(元素为n时)。
这里面有很多重复情况,我想只计算一次。
所有的序列都能被分成size-1和1,然后把他们加起来。//全部算出来估计是不可能。。。
递归写不出来,先换种想法
button-up
一开始只有一个元素,大于0就留下,小于0就不留下。
然后加上第二个元素,小于0就不留下,大于0就继续加。
唯独没考虑到,最终结果是负数怎么办?
int maxSubArray(int* nums, int numsSize) {
int p=0;
int t=0;
int j=0;
int a[1000000]={0};
if(numsSize==1)
return nums[0];
if(nums[0]>0)
p=nums[0];
for(int i=1;i<numsSize;i++){
t=p+nums[i];
if(t<0){
p=0;
}
else{
if(p!=0){
a[j]=p;
j++;
}
p=t;
}
a[j]=p;
}
p=max(a,j,p);
return p;
}
int max(int a[],int j,int p){
int t=0;
if(j==0)
return p;
for(int i=0;i<j;i++){
if(a[i]>t)
t=a[i];
}
return t;
}
还是想递归吧。