大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > Java技巧 > 求首尾相连数组的最大子序列和

求首尾相连数组的最大子序列和


[摘要]本文主要是对求首尾相连数组的最大子序列和的讲解,希望对大家学习求首尾相连数组的最大子序列和有所帮助。

  题目描述:

  给定一个由N个整数元素组成的数组arr,数组中有正数也有负数,这个数组不是一般的数组,其首尾是相连的。数组中一个或多个连续元素可以组成一个子数组,其中存在这样的子数组arr[i],…arr[n-1],arr[0],…,arr[j],现在请你这个ACM_Lover用一个最高效的方法帮忙找出所有连续子数组和的最大值(如果数组中的元素全部为负数,则最大和为0,即一个也没有选)。

  输入:

  输入包含多个测试用例,每个测试用例共有两行,第一行是一个整数n(1=

  输出:

  对于每个测试用例,请输出子数组和的最大值。

  样例输入:

  6

  1 -2 3 5 -1 2

  5

  6 -1 5 4 -7

  样例输出:

  10

  14

  最容易想到的算法:

  #include<CSTDIO>

  #define MAX 100005

  using namespace std;

  int main(int argc,char *argv[])

  {

  int i,j,k;

  int array[MAX];

  int n;

  while(scanf("%d",&n)!=EOF)

  {

  int flag=0;

  for(i=0;i<N;I++) if(array[i] scanf(?%d?,&array[i]); {>=0)

  flag=1;

  }

  long long sum;

  long long max=-1001;

  for(i=0;i<N;I++) { if(sum sum+="array[j];" sum="array[i];" if(sum<0) for(j="i+1;j<n;j++)">max)

  max=sum;

  }

  for(k=0;k<I;K++) { if(sum sum+="array[k];" sum="0;" if(sum<0)>max)

  max=sum;

  }

  }

  if(flag)

  printf("%lld\n",max);

  else

  printf("0\n");

  }

  return 0;

  }

 

  很不幸,该算法的时间复杂度为O(n*n),结果可想而知超时了…那么有木有复杂度为O(n)的算法呢?答案是肯定的首先我们来分析一下,无非存在以下两种情况: 1,最大子序列没有跨过最后一个元素,那就好办了,就是前面提到过的最大子序列和 2,最大子序列跨过了最后一个元素,那么又该怎么解决呢?不妨换个思路想一想,求出序列的最小子序列,对于跨过最后一个元素的情况下,那么最小子序列一定是负数。那就好办了,只要求出这两种情况下的较大者就行了。还可以再进行一下转换:对于跨过最后一个元素的情况有 maxsum=sum-minsum即最大子序列和等于全部的和减去最小子序列的和。 AC代码:

  #include<CSTDIO>

  #define MAX 100005

  using namespace std;

  int Array[MAX];

  int MaxSum(int n)

  {

  int i,sum=0;

  int max=-0xFFFFFFF;

  sum+=Array[0];

  for(i=1;i<N;I++) { if(sum sum+="Array[i];" sum="Array[i];" if(sum<0) else>max)

  max=sum;

  }

  return max;

  }

  int MinSum(int n)

  {

  int i,sum=0;

  int min=0xFFFFFFF;

  sum+=Array[0];

  for(i=1;i<N;I++) { if(sum>0)

  sum=Array[i];

  else

  sum+=Array[i];

  if(sum<MIN) { sum+="Array[i];" sum="0;" ans="0;" negative are numbers all if(maxsum<0) minsum="MinSum(n);" int maxsum="MaxSum(n);" ans; } scanf(?%d?,&Array[i]); i="0;i<n;i++)" for(int while(scanf(?%d?,&n)!="EOF)" n; *argv[]) argc,char main(int min; return min="sum;">(sum-minsum)?maxsum:(sum-minsum);

  printf("%d\n",ans);

  }

  return 0;

  }



相关评论