算法-最大连续子序列和
题目:给定(可能是负的)整数A1、A2、…、AN,求出并确定对应的序列的最大值。如果所有的整数都是负数,那么最大连续子数列和就是0,只是求出最大值,不需要求出具体的序列,作为这个题目的变种有很多情况下给你一个确定的数列,具体求和,大同小异,共有四种解法,按照时间复杂度来解,object-c实现,解法如下:
穷举法
这个应该是这个题目最容易想到的方式,通过循环遍历出所有的序列组合,求出最大的序列的最大值,代码如下:
-(NSInteger)maxSubsequenceSum:(NSArray *)data{ NSInteger maxSum=0;//最大子序列的和 for (NSInteger start=0; start<[data count]; start++) { for (NSInteger end=start; end<[data count]; end++) { NSInteger currentSum=0;//当前子序列的和 //data[start]~data[end]子序列的和 for (NSInteger i=start; i<=end; i++) { currentSum+=[[data objectAtIndex:i] integerValue]; } //通过判断给最大子序列的和赋值 if (maxSum<currentSum) { maxSum=currentSum; } } } return maxSum; }
这个算法三个循环,假设数组的长度为n,第一层循环为n,第二层循环n-start,第三层end-start,可算出时间复杂度O(n*n*n)=O(N^3),时间复杂度是跟输入长度的立方有关,如果数组过长会是一个灾难~
穷举精简版
对data[start]~data[end]子序列求和,可以由上一次求和data[start]~data[end-1]的结果加上data[end]得到,不需要重头开始计算,时间复杂度为O(N^2)
-(NSInteger)maxSubsequenceSumSecond:(NSArray *)data{ NSInteger maxSum=0;//最大子序列的和 for (NSInteger start=0; start<[data count]; start++) { NSInteger currentSum=0;//当前子序列的和 for (NSInteger end=start; end<[data count]; end++) { //data[start]~data[end]子序列的和,通过end加入,不需要循环 currentSum+=[[data objectAtIndex:end] integerValue]; if (maxSum<currentSum) { maxSum=currentSum; } } } return maxSum; }
递归版
题目中最大子序列可能在三个地方出现,左半部,右半部,跨越输入数据的中部而占据左右两部分。前两种情况递归求解,第三种情况的最大和可以通过求出前半部分最大和(包含前半部分最后一个元素)以及后半部分最大和(包含后半部分的第一个元素)相加而得到。
-(NSInteger)maxSubsequenceSumThird:(NSArray *)data leftIndex:(NSInteger)left rightIndex:(NSInteger)right{ if (left==right) { if (data[left]>0) { //空集也算是子序列,空集和为0,最大子序列和最小为0 return [data[left] integerValue]; }else{ return 0; } } NSInteger center=(left+right)/2; NSInteger maxLeftSum=[self maxSubsequenceSumThird:data leftIndex:left rightIndex:center]; NSInteger maxRightSum=[self maxSubsequenceSumThird:data leftIndex:center+1 rightIndex:right]; //左半部分中包含最右边元素的子序列的最大和 NSInteger maxLeftBorderSum=0,leftBorderSum=0; for (NSInteger i=center; i>=left; i--) { leftBorderSum+=[data[i] integerValue]; if (leftBorderSum>maxLeftBorderSum) { maxLeftBorderSum=leftBorderSum; } } //右半部分包含最左边的值 NSInteger maxRightBorderSum=0,rightBorderSum=0; for (NSInteger i=center+1;i<right;i++) { rightBorderSum+=[data[i] integerValue]; if (rightBorderSum>maxRightBorderSum) { maxRightBorderSum=rightBorderSum; } } //跨越左右部分的最大序列和 NSInteger maxMiddleSum=maxLeftBorderSum+maxRightBorderSum; //左部分,右部分,跨越左右的最大序列和的最大值 NSInteger result=maxLeftSum>maxRightSum?maxLeftSum:maxRightSum; return result>maxMiddleSum?result:maxMiddleSum; }
如果left==right,那么T(1)=1,两层循环的时间的次数2/N,最后的时间复杂度T(N)=2T(N/2)+O(N),等价于2T(N/2)+N,T(N)=N*(K+1)(这个可以自己推导),T(N)=N*(k+1)=NlogN +N=O(N );
最简版
一次遍历,如果小于0,重新设置循环的位置,时间复杂度O(N):
-(NSInteger)maxSubsequenceSumFour:(NSArray *)data{ NSInteger maxSum=0,currentSum=0; for (NSInteger index=0; index<[data count]; index++) { currentSum+=[[data objectAtIndex:index] integerValue]; //判断当前序列的和是否为正数 if (currentSum<0) { currentSum=0; } else if(maxSum<currentSum) { maxSum=currentSum; } } return maxSum; }
还有一个极端的情况,如果都是负数,不想返回0,获取最大的负整数即可:
-(NSInteger)maxSubsequenceSumSpecial:(NSArray *)data{ NSInteger maxSum=[[data objectAtIndex:0] integerValue],currentSum=0; NSInteger maxNegative=[[data objectAtIndex:0] integerValue]; for (NSInteger index=0; index<[data count]; index++) { currentSum+=[[data objectAtIndex:index] integerValue]; if (currentSum<0) { currentSum=0; } else if(maxSum<currentSum) { maxSum=currentSum; } if (maxNegative<[data[index] integerValue]) { maxNegative=[data[index] integerValue]; } } return maxSum>maxNegative?maxSum:maxNegative; }
调用如下:
NSArray *dataSource=[[NSArray alloc]initWithObjects:@"10",@"-9",@"-3",@"8",@"-2", nil]; MaxSubsequence *maxSubsequence=[[MaxSubsequence alloc]init]; NSInteger result=[maxSubsequence maxSubsequenceSum:dataSource]; NSLog(@"最大的连续子序列的和:%ld",(long)result); NSInteger resultSecond=[maxSubsequence maxSubsequenceSumSecond:dataSource]; NSLog(@"第二种最大的连续子序列的和:%ld",(long)resultSecond); NSInteger thirdResult=[maxSubsequence maxSubsequenceSumThird:dataSource leftIndex:0 rightIndex:dataSource.count-1]; NSLog(@"第三种最大的连续子序列的和:%ld",(long)thirdResult); NSInteger fourResult=[maxSubsequence maxSubsequenceSumFour:dataSource]; NSLog(@"第四种最大的连续子序列的和:%ld",(long)fourResult); NSInteger specialResult=[maxSubsequence maxSubsequenceSumSpecial:dataSource]; NSLog(@"第四种全是负数最大的连续子序列的和:%ld",(long)specialResult);
结果是10,数组简单定义下,重要是看过程~
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。