👨‍🎓作者简介：一位喜欢写作，计科专业大二菜鸟一枚
🏡个人主页：starry陆离
🕒首发日期：2022年5月7日星期六
📚订阅专栏：算法分析与设计
如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦

🍀【动态规划】最大子段和

• 1️⃣问题引入（恒生电子笔试题）
• 2️⃣问题描述
• 3️⃣两种设计方法
• • 穷举法
  • 动态规划法
• 4️⃣升级版最大字段和

1️⃣问题引入（恒生电子笔试题）

输入一个整型数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都
有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1，-2，3，10，-4，7，2，-5，和最大的子数组为3，10，-4，7，2，因此输出为该子数组的 和18。

2️⃣问题描述

• 给定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

3️⃣两种设计方法

• 以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个连续字串

穷举法

对所有的(i,j)对，顺序求和a[i]+...+a[j]并比较出最大的和

时间复杂度：O(n^3 )

import java.util.Scanner;public class Main1 {public static void main(String[] args) {Scanner scanner=new Scanner(System.in);int n=scanner.nextInt();int[] num=new int[n];for(int i=0;i<n;++i) {num[i]=scanner.nextInt();}int max=Solve(num);System.out.println(max);scanner.close();}    //穷举法private static int Solve(int[] num) {int len=num.length;int max=0;for(int i=0;i<len;++i) {for(int j=i;j<len;++j) {int t=0;for(int k=i;k<=j;++k) {t+=num[k];}if(t>max) {max=t;}}}return max;}}

算法改进

时间复杂度：O(n^2)

private static int SloveImp(int[] num) {int len=num.length;int max=0;for(int i=0;i<len;++i) {int t=0;for(int j=i;j<len;++j) {t+=num[j];if(t>max) {max=t;}}}return max;}

动态规划法

• 若记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)

例题：HNUCM-OJ最大字段和

private static int DpSolve(int[] num) {int len=num.length;int max=-99999;int b[]=new int[len];b[0]=num[0];for(int i=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];}}return max;}

4️⃣升级版最大字段和

例题：HNUCM-OJ最大字段和升级版

输出最大子段和，以及子段的起始位置和结束位置：

例如：输入数组(6,-1,5,4,-7)，输出14, 1, 4，其中14表示最大子段和，1 表示和最大的子段从第1个数字开始，4表示和最大的子段到第4个数字结 束，即(6, -1 , 5, 4)

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner=new Scanner(System.in);int n;int num[];int []b;int end;int max;while(scanner.hasNext()) {n=scanner.nextInt();num=new int[n];for(int i=0;i<n;++i) {num[i]=scanner.nextInt();}//dp数组b=new int[n];b[0]=num[0];//记录结束位置end=0;//最大值初始值为第一个元素max=num[0];     //动态规划for(int i=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;}}int k=max;//记录起始位置int begin=0;//当k==0时，说明找到了起始位置点for(int i=end;k!=0;--i) {k-=num[i];begin=i;}System.out.println(max+" "+(begin+1)+" "+(end+1));}scanner.close();}}