问题引入（恒生电子笔试题）
输入一个整型数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如输入的数组为1，-2，3，10，-4，7，2，-5，和最大的子数组为3，10，-4，7，2，因此输出为该子数组的和18。
问题描述
- 给定n个整数（可能是负数）组成的序列
a[1], a[2], a[3], …, a[n]，求该序列 的子段和，例如a[i]+a[i+1]+…+a[j]的最大值 - 当所给的整数均为负数时定义子段和为0，依此定义，所求的最优值为：
max{0, a[i]+a[i+1]+…+a[j]}, 1<=i<=j<=n - 例如，当（a[1],a[2],a[3],a[4],a[5],a[6]）=(-2,11,-4,13,-5,-2)时，最大子段 和为20，即 20 = 11 + (-4) + 13
网络异常，图片无法展示
|
三种设计方法
- 以a1开始：{a1 }, {a1 ,a2 }, {a1 ,a2 ,a3 }……{a1 ,……an }，共n个
- 以a2开始：{a2 }, {a2 ,a3 }, {a2 ,a3 ,a4 }……{a2 ,……an }，共n-1个
- ......
- 以an开始：{an }，共1个
一共有（n+1)*n/2个连续字串
穷举法T(n)=O(n3)
对所有的(i,j)对，顺序求和a[i]+...+a[j]并比较出最大的和
时间复杂度：O(n^3 )
importjava.util.Scanner; publicclassMain1 { publicstaticvoidmain(String[] args) { Scannerscanner=newScanner(System.in); intn=scanner.nextInt(); int[] num=newint[n]; for(inti=0;i<n;++i) { num[i]=scanner.nextInt(); } intmax=Solve(num); System.out.println(max); scanner.close(); } //穷举法privatestaticintSolve(int[] num) { intlen=num.length; intmax=0; for(inti=0;i<len;++i) { for(intj=i;j<len;++j) { intt=0; for(intk=i;k<=j;++k) { t+=num[k]; } if(t>max) { max=t; } } } returnmax; } }
算法改进
时间复杂度：O(n^2)
privatestaticintSloveImp(int[] num) { intlen=num.length; intmax=0; for(inti=0;i<len;++i) { intt=0; for(intj=i;j<len;++j) { t+=num[j]; if(t>max) { max=t; } } } returnmax; }
分治法
将数组分成左右两半，分别计算左边的最大和、右边的最 大和、跨边界的最大和，然后比较其中最大者
动态规划法T(n)=O(n)
- 若记
b[j]=max(a[i]+a[i+1]+..+a[j])，b[j]表示以a[j]作为最后一个元素的最 大子段和，其中1<=i<=j，并且1<=j<=n，则所求的最大子段和为 max{b[j]}，1<=j<=n - 由b[j]的定义可易知，当b[j-1]>0时
b[j]=b[j-1]+a[j]，否则b[j]=a[j]。故 b[j]的动态规划递归式为:
b[j]=max(b[j-1]+a[j], a[j])，1<=j<=n
网络异常，图片无法展示
|
时间复杂度：O(n)
privatestaticintDpSolve(int[] num) { intlen=num.length; intmax=-99999; intb[]=newint[len]; b[0]=num[0]; for(inti=1;i<len;++i) { if(b[i-1]>0) { b[i]=b[i-1]+num[i]; }else { b[i]=num[i]; } if(b[i]>max) { max=b[i]; } } returnmax; }
升级版最大字段和
输出最大子段和，以及子段的起始位置和结束位置：
- 例如：输入数组(6,-1,5,4,-7)，输出14, 1, 4，其中14表示最大子段和，1 表示和最大的子段从第1个数字开始，4表示和最大的子段到第4个数字结 束，即(6, -1 , 5, 4)
importjava.util.Scanner; publicclassMain { publicstaticvoidmain(String[] args) { Scannerscanner=newScanner(System.in); intn; intnum[]; int []b; intend; intmax; while(scanner.hasNext()) { n=scanner.nextInt(); num=newint[n]; for(inti=0;i<n;++i) { num[i]=scanner.nextInt(); } //dp数组b=newint[n]; b[0]=num[0]; //记录结束位置end=0; //最大值初始值为第一个元素max=num[0]; //动态规划for(inti=1;i<n;++i) { if(b[i-1]>0) { b[i]=b[i-1]+num[i]; }else { b[i]=num[i]; } if(b[i]>max) { max=b[i]; end=i; } } intk=max; //记录起始位置intbegin=0; //当k==0时，说明找到了起始位置点for(inti=end;k!=0;--i) { k-=num[i]; begin=i; } System.out.println(max+" "+(begin+1)+" "+(end+1)); } scanner.close(); } }
