题解 | 最大子段和

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner=new Scanner(System.in);
		int n=scanner.nextInt();
		long a[]=new long[n];
		for (int i = 0; i < a.length; i++) {
			a[i]=scanner.nextLong();
		}
		long dp[]=new long[n+5];
		//dp[i]表示以a[i]结尾的最大子数组和
		dp[1]=a[0];
		long max=a[0];
		for (int i = 2; i <= n; i++) {
			//要么自成一派，要么加入组织
			dp[i]=Math.max(a[i-1], dp[i-1]+a[i-1]);
			if(dp[i]>max)max=dp[i];
		}
		System.out.println(max);
		

	}

}

把dp[i]设置为以a[i]结尾的最大子段和，那么当考虑a[i]时，要么独自成一组，要么加入之前的子段，如果之前的子段和是正数，那么一般就加入，如果是负数，那么独自一组