53. 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.

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;
}

还是想递归吧。