试题 算法提高 最大连续子段和

问题描述
　　给出一个长为n的数列，a1，a2，……，an，求和最大的连续子序列，即找到一对（i，j），i<=j，使 ai+ai+1+……+aj 的和最大，输出这个和
输入格式
　　第一行为正整数n
　　第二行n个用空格分开的整数
　　表示a1，a2，……，an
输出格式
　　一个整数，表示最大连续子序列的和
样例输入
3
-1 -2 -3
样例输出
-1
数据规模和约定
　　1 <=n <= 10⁵， -10⁵ <= ai<= 10⁵
　　
题目链接：最大连续子段和

分析：

1.隐式要求：

从数据规模可以分析出:
  最大和为10⁵ * 10⁵ = 10¹⁰ ，超过了 int 型的数据范围(10⁹)，那么存最大和的变量的数据类型应设置为 long 型。(虽然我用int型测试也能通过，但为了严谨性，最好还是设置为 long 型)。
  n² <= 10¹⁰ ，那么若用时间复杂度为$O$(n²)的算法，那么会超时。计算机 1s 能处理的规模大概为10⁸ 左右，所以算法的时间复杂度应为$O(nlogn)$及以下。

2.解决思路

使用动态规划（DP）来解决。
  $nums[i]$表示第 i 个数。
  $dp[i]$ 表示把第 i 个数算上，能得到的最大和。

状态转移方程：
$dp[i]=max(dp[i-1]+nums[i],nums[i])$

下面举个例子说明状态转移方程。
若数据为 $8,4,-15,-12,10,20$，那么dp[1] = 8, dp[2] = 12，dp[3] = -3，计算dp[4]时，不加上dp[3]反而更大，所以dp[4]就为-12，dp[5]同理为10，这样才能得到最大和为dp[6] = 30。

代码：

import java.util.Scanner;

public class Main {
	//提前创建最大容量的数组，以免后续再new数组对象的操作
	static int[] nums = new int [100005];
	static int[] dp = new int[100005];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		for( int i = 1; i <= n; i++)
			nums[i] = sc.nextInt();
		
		//初始化dp[1]为第一个数字
		dp[1] = nums[1];
		//存最大值的变量，初始化为dp[1]
		long max = dp[1];
		for (int i = 2; i <= n; i++) {
			dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
			//在这里更新最大值，以免后面再扫描一遍dp数组找最大值
			max = Math.max(max, dp[i]);
		}
		System.out.println(max);
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25