题解 | 最大子段和

最大子段和，我们需要构造出一个dp数组，其中dp[i]表示以a[i]结尾的最大值，要么为dp[i-1]+a[i]，要么为a[i]

import java.util.ArrayList;
import java.util.Arrays;
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();
		int a[]=new int[n];
		int flag=0;
		for (int i = 0; i < a.length; i++) {
			a[i]=scanner.nextInt();
			if(a[i]>0) {
				flag=1;
			}
		}
		long max=Integer.MIN_VALUE;
		long dp[]=new long[n];
		dp[0]=a[0];
//		这里的dp[i]表示以a[i]结尾的最大值
		for (int i = 1; i < dp.length; i++) {
			dp[i]=Math.max(dp[i-1]+a[i], a[i]);
			if(dp[i]>max) {
				max=dp[i];
			}
		}
		System.out.println(max);

	}

}