求解最大连续子序列和问题----蛮力法

文章预览

• • 问题：求解最大连续子序列和问题
  • • 思路一：穷举法
    • 思路二：穷举法
    • 思路三：穷举法

问题：求解最大连续子序列和问题

题目：

给定一个有n（n>=1）个整数的序列，求解其中最大连续子序列的和。规定一个序列的最大子序列和至少为0，若结果小于0，则其结果为0

例：序列（-2,11,-4,13,-5,-2）的最大子序列和为20序列（-6，2,4，-7,5,3,2，-1,6，-9,10，-2）的最大子序列和为16。

思路一：穷举法

• 时间复杂度O（n^3）

设含有n个整数的序列a[0 … n-1]和其中任何连续子序列a[i … j]（i<=j,0<=i<=n-1,i

参考代码

#include<stdio.h>int Maxsum(int a[],int n){int i,j,k;int maxSum=0,curSum;for(i=0;i<n;i++){for(j=i;j<n;j++){curSum=0;for(k=i;k<=j;k++)curSum+=a[k];if(curSum>maxSum)maxSum=curSum;}}return maxSum;
}
int main(){int a[]={-2,11,-4,13,-5,-2};int n=sizeof(a)/sizeof(a[0]);int b[]={-6,2,4-7,5,3,2,-1,6,-9,10,-2};int m=sizeof(b)/sizeof(b[0]);printf("a序列最大和：%ld\n",Maxsum(a,n));printf("b序列最大和：%ld\n",Maxsum(b,m));
}

思路二：穷举法

• 时间复杂度O（n^2）

在求两个相邻子序列和时它们之间是相关联的

例：Sum（a[i … j]）表示a[i … j]中所有元素的和，Sum（a[0 … 3]）=a[0]+a[1]+a[2]+a[3],而Sum（a[4]=a[0]+a[1]+a[2]+a[3]+a[4]）

这样做，在前者计算出来后求后者时只需在前者的基础上加a[4]即可，不需要每次重复计算。

Sum(a[i ... j])=0;   //a[i ... j] 没有元素Sum(a[i ... j])=a[i ... j-1]+a[j]   //a[i ... j] 有元素

参考代码

#include<stdio.h>int Maxsum(int a[],int n){int i,j;int maxSum=0,curSum;for(i=0;i<n;i++){curSum=0;for(j=i;j<n;j++){curSum+=a[j];if(curSum>maxSum)maxSum=curSum;}}return maxSum;
}int main(){int a[]={-2,11,-4,13,-5,-2};int n=sizeof(a)/sizeof(a[0]);int b[]={-6,2,4-7,5,3,2,-1,6,-9,10,-2};int m=sizeof(b)/sizeof(b[0]);printf("a序列最大和：%ld\n",Maxsum(a,n));printf("b序列最大和：%ld\n",Maxsum(b,m));
}

思路三：穷举法

• 时间复杂度O(n)

从头开始扫描数组a，用curSum（初值为0）记录当前子序列之和，用maxSum（初值为0）记录最大连续子序列之和。
如果在扫描中遇到负数，当前子序列和curMax会减小，若curMax为负数，表明前面已经扫描到的那个子序列可以抛弃，则放弃这个子序列，重新开始下一个子序列的分析，并置maxSum=0.若这个子序列和curSum不断增加，那么最大子序列和maxSum也不断增加.

参考代码

#include<stdio.h>int Maxsum(int a[],int n){int i;int maxSum=0,curSum=0;for(i=0;i<n;i++){curSum+=a[i];if(curSum<0)curSum=0;if(maxSum<curSum)maxSum=curSum;}return maxSum;
}int main(){int a[]={-2,11,-4,13,-5,-2};int n=sizeof(a)/sizeof(a[0]);int b[]={-6,2,4-7,5,3,2,-1,6,-9,10,-2};int m=sizeof(b)/sizeof(b[0]);printf("a序列最大和：%ld\n",Maxsum(a,n));printf("b序列最大和：%ld\n",Maxsum(b,m));
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！