[编程题]连续子数组的最大和
毕业设计
1
输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
数据范围:
1<=n<=1051 <= n <= 10^5**1**<**=**n**<**=**1**0**5**
−100<=a[i]<=100-100 <= a[i] <= 100**−**1**0**0**<**=**a**[**i**]**<**=**1**0**0**
要求:时间复杂度为 O(n)O(n) O ( n )，空间复杂度为 O(n)O(n) O ( n )
进阶:时间复杂度为 O(n)O(n) O ( n )，空间复杂度为 O(1)O(1) O ( 1 )
示例1
输入
[1,-2,3,10,-4,7,2,-5]
输出
18
说明
经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18
示例2
输入
[2]
输出
2
示例3
输入
[-10]
输出
-10
-
/* 算法时间复杂度O（n） 用total记录累计值，maxSum记录和最大 基于思想：对于一个数A，若是A的左边累计数非负，那么加上A能使得值不小于A，认为累计值对 整体和是有贡献的。如果前几项累计值负数，则认为有害于总和，total记录当前值。 此时 若和大于maxSum 则用maxSum记录下来 */ public class Solution { public int FindGreatestSumOfSubArray(int[] array) { if(array.length==0) return 0; else{ int total=array[0],maxSum=array[0]; for(int i=1;i<array.length;i++){ if(total>=0) total+=array[i]; else total=array[i]; if(total>maxSum) maxSum=total; } return maxSum; } } } -
//动态规划 int FindGreatestSumOfSubArray(vector<int> array) { if(array.empty()) return 0; int sum = array[0], tempsum = array[0]; //注意初始值 不能设为0 防止只有负数 for(int i = 1; i < array.size(); i++) //从1开始 因为0的情况在初始化时完成了 { tempsum = (tempsum < 0) ? array[i] : tempsum + array[i]; sum = (tempsum > sum) ? tempsum : sum; } return sum; }
发表回复