首页 > 其他 > 详细

求一串数字中——和最大的连续子序列

时间:2014-02-17 19:51:37      阅读:586      评论:0      收藏:0      [点我收藏+]

问题描述 :
从一组数字中,找出其所有连续子序列中,和数(子序列所有数字求和)最大的连续子序列:

如:数组 int A[ ] = {-4 , 3 , 5 , -1};找出某几个连续的子序列其和最大。比如A0+A1 = -1 。A1+A2+A3+A4 = 3。而A2+A3=8;则A2 A3组成的数组即是所求。

 

求解方法1:

 

先写我自己的方法,不是动态规划,复杂度大概是O(n*n);

1,二维数组ret[ ][ ];用上面的例子中数组A[ ]= {-4 , 3 , 5 , -1}为例:

        ~  -4   3   5   1

0        0   0   0   0   0     //为了方便计算,第0行第0列均设为0

1        0  -4   3   5   1     //第1行表示子串长度为1时,包含该位置元素的子序列和数

2        0       -1   8   6     //第2行表示子串长度为2时,包含该位置元素的子序列和数

3        0             4   9

4        0                  5

其中,ret[i][j]位置的值为ret[i-1][j-1] + inp[j-1];

原理是,包含某个数x的子串长度为k的最大和数,等于x加上x之前的子串长度为k-1的最大和数;

即:上表中ret[4][5]=4,它是子序列长度为3,包含j=5处元素(即inp[4])的最大和数,是第5列以前的所有子序列长度为3-1=2的序列中,最大和数+该位的值:ret[3][4] + inp[4]=-1+5=4;

也就是说子序列长度为i的包含第j个位置的最大和数,是基于子序列长度为i-1的j前面的最大和数来求得的;

bubuko.com,布布扣
#include<stdlib.h>
#include<stdio.h>
#define MAX 100 

int ret[MAX][MAX] = {{0}};//len+1行len+1列
int maxSubSeqSum(int inp[],int len){
        int maxret = 0;//最大的顺序子串和的值
        int i = 1;//第0行和第0列都为0
        for(;i<len+1;i++){
                int j=i;
                for(;j<len+1;j++){
                        ret[i][j] = ret[i-1][j-1] + inp[j-1];
                        //ret由于第0行第0列值都为0,所以inp需要j-1
                        if(ret[i][j] > maxret) maxret = ret[i][j];
                        printf("ret[%d][%d]=%d\n",i,j,ret[i][j]);
                }
        }
        return maxret;
}

int main(){
        int input[] = {1,-1,4,-3,2};
        int len = sizeof(input)/sizeof(int);
        int ret = maxSubSeqSum(input,len);
        printf("max sub sequence sum is:%d\n",ret);
        return 0;
}
bubuko.com,布布扣

 

运行结果:

xu@xu-ThinkPad-X61:~/algorithm$ gcc maxSubSeqSum.c
xu@xu-ThinkPad-X61:~/algorithm$ ./a.out
ret[1][1]=1
ret[1][2]=-1
ret[1][3]=4
ret[1][4]=-3
ret[1][5]=2
ret[2][2]=0
ret[2][3]=3
ret[2][4]=1
ret[2][5]=-1
ret[3][3]=4
ret[3][4]=0
ret[3][5]=3
ret[4][4]=1
ret[4][5]=2
ret[5][5]=3
max sub sequence sum is:4

 

 

求解方法2:

 

1,递归公式:f(n)表示包含元素A(n)的最大子序列和,它的最大值,要么=A(n),要么=

A(n)+f(n-1);

2,复杂度为O(n);

bubuko.com,布布扣
#include<stdlib.h>
#include<stdio.h>
#define max(a,b) (a>b)?a:b

int maxSubSeqSum(int inp[],int inplen){
        int presum=*inp,ret=0,i=1;//ret为最大和,presum是f(n-1)的值
        for(;i<inplen;i++){
                presum += inp[i];
                int tmpmax = max(presum,inp[i]);
                if(tmpmax > ret) ret=tmpmax;
        }
        return ret;
}

int main(){
        int input[]={1,-1,4,-3,2};
        int length = sizeof(input)/sizeof(int);
        int ret =maxSubSeqSum(input,length);
        printf("result is:%d\n",ret);
        return 0;
}
bubuko.com,布布扣

xu@xu-ThinkPad-X61:~/algorithm$ ./a.out
result is:4

 

 

 

求一串数字中——和最大的连续子序列

原文:http://www.cnblogs.com/McQueen1987/p/3552021.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!