最大子序列问题

问题

给定n个整数(可能是负数)的序列{a1,a2,…a3},求其子序列的相加的最大值,负数就为0

e.g. -1 , 3 , -2 , 4 , -6 , 1 , 6 , -1
最大值:7

解决

直接法

把所有子序列列出来相加,然后判断最大值

int findMax(int a[],int l){
int max = 0;//最大值 
int s = 0;  //序列和 
for(int i=0;i<l;i++){
for(int j=i;j<l;j++){
for(int z=i;z<j;z++){
                s+=a[z];
            } 
if(s>max){
                max=s;
            }   
            s=0;
        } 
    }
return max;
}

时间复杂度 O(n^3)

直接法(改进)

全部子序列列出来,相加,在子序列相加的时候进行的小部分优化
上一个方法缺点:
    第一轮: i=0 , j=1 , s=-1
    第二轮: i=0 , j=2 , s=-1+3
    第三轮: i=0 , j=3 , s=-1+3+-2
    第四轮: i=0 , j=4 , s=-1+3+-2+4
     …
    即那有些重复相加的部分可以省略

int findMax(int a[],int l){
int max = 0;//最大值 
int s = 0;  //序列和 
for(int i=0;i<l;i++){
for(int j=i;j<l;j++){
            s+=a[j];   
if(s>max){
                max=s;
            }       
        } 
        s=0;
    }
return max;
}

时间复杂度O(n^2)

分治法

前面的时间复杂度太高，对于大数据的处理事件会很长

分治法:也就是把大问题转化成若干个小问题，再把小问题各个击破，再结合小问题解决得到大问题的解决

把这个序列分成3部分 , 左边序列(leftMax)，中间序列(midMax)，右边序列(rightMax)，再判断这3种序列中的最大值

图解:
1.
黄色区域
    leftMax = -1 rightMax = 3 midMax=-1+3=2
    这里可以看出黄色区域最大序列为3
绿色区域
    leftMax = -2 rightMax = 4 midMax=-2+4=2
    这里可以看绿色区域最大序列为2

2.
    leftMax = 3 rightMax = 2 midMax=3+-2+4=5
    这里可以看出区域最大序列为5

3.

同理

中间序列取值是从分开位置开始(见图3)
    取左边最大4+-2+3=5
    取右边最大-6+1+6=1
则中间序列取值为5+1=6
```
int findMax(int a[],int l,int r){

int mid = (l+r)/2;
//当序列分到只有一个值,或者这个序列只有一个值 
if(l==r){
return a[l]>0?a[l]:0;
    }

int leftMax = findMax(a,l,mid);
int rightMax = findMax(a,mid+1,r);

int leftxMax=0,rightxMax=0,ls=0,rs=0; 

for(int i=mid;i>=l;i--){
        leftxMax+=a[i];
if(leftxMax>ls){
            ls=leftxMax;
        }
    } 

for(int i=mid+1;i<r;i++){
        rightxMax+=a[i]; 
if(rightxMax>rs){
            rs=rightxMax;
        }   
    }
int midMax= ls+rs;

int max1 = leftMax>midMax?leftMax:midMax;
int max = rightMax>max1?rightMax:max1;

return max;
}
```
时间复杂度:Tn=T(n/2)+T(n/2)+cN 即:左边完成+右边完成+中间完成
                      =2T(n/2)+cN
                      =2T(2T(n/4)+cN/4)+cN
                      …
                      =2^k*T(n/2^k+cN/2^k)+cN
                      T(n/2^k) 趋向与1 k=lgN
                      =O(N*lg2)

动态规划(贪心)
比上一个时间复杂度更低

最大子序列和中的每个子序列和都大于0

证明:
前提a1+a2+a3+a4位最大子序列和
假设有a1+a2<0,则a1+a2+a3+a4不为为最大子序列和,最大子序列应该为a3+a4

int findMax(int a[],int l){
int max=0;//最大值 
int s = 0;  //序列和
for(int i=0;i<l;i++){
        s+=a[i];
if(s>0&&s>max){
            max=s;
        }
if(s<0){
            s=0;
        }
    }
return max;
}

时间复杂度:O(n)

秒客网

最大子序列问题

问题

解决

直接法

直接法(改进)

分治法

相关文章