子数组的最大和[算法]
题目:输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的
和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,因此输出为该子数组的和18。
这个题我的第一感觉就是3层for循环直接进行么,就喜欢暴力for循环,遍历所有可能,还是自己的想法太low
了,其实这个题的时间复杂的度可以变为o(n),下面的代码分别用3个不一样的时间复杂度完成的题,所以代码敲完要 优化,也要问一下其他,自己的代码不一定很棒棒哒。废话也就不多说了,因为这个算法比较简单,所以不多做解释了。
1 时间复杂度为o(n^3)
#include <stdio.h> #include<stdlib.h> int main(){ int n,t; int *a; int i,j; int x=0,y=0,m; int max=0,sum=0; scanf("%d",&n); a=(int *)malloc(sizeof(int)*n); for(i=0;i<n;i++) scanf("%d",a+i); for(i=0;i<n;i++) { for(j=0;j<n;j++) { m=j; sum=0; for(int k=0;k<i;k++) sum+=a[m++]; if(max<sum) { max=sum; x=i; y=j; } } } printf("x=%d,y=%d\n",x,y); if(x>y){t=x;x=y;y=t;} //如果x>y ,就进行交换 for(i=x;i<=y+1;i++) //这里+1,是因为数组虽然标记的数加+1才是实际的个数 printf("%d ",a[i]); printf("\nmax=%d\n",max); return 0; }
2 时间复杂度为o(n^2)
#include<stdio.h> #include<stdlib.h> int main() { int n; int *a; int i,j; int sum=0,max=0; scanf("%d",&n); a=(int *)malloc(sizeof(int)*n); for(i=0;i<n;i++) scanf("%d",a+i); for(i=0;i<n;i++) { sum=0; // sum每次置0 for(j=i;j<n;j++) { sum+=a[j]; if(max<sum) max=sum; } } printf("max=%d\n",max); return 0; }
时间复杂度为o(n)
#include<stdio.h> #include<stdlib.h> int main() { int n; int *a; int i; int sum=0,bettersum=0; scanf("%d",&n); a=(int *)malloc(sizeof(int)*n); for(i=0;i<n;i++) scanf("%d",a+i); for(i=0;i<n;i++){ sum+=a[i]; //如果当前和值为零,则把当前和值置为零 if(sum<0) sum=0; //如果当前和值大于最优值,则最优值记录当前和值 if(bettersum<sum) bettersum=sum; } //如果数组全为负值,只需要找到一个最大的负值 if(0==bettersum) { bettersum=a[0]; for(i=0;i<n;i++){ if(a[i]>bettersum) bettersum=a[i]; } } printf("bettersum=%d\n",bettersum); return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。