解题步骤

1.确定状态

数组下标不断移动，在移动过程中，最大子数组也不断变化，所以状态为子数组最大值。

2.确定dp数组

在本题中，可定义一维数组dp[x]，其中dp[i]表示以第i个元素结尾最大子数组的值

3.确定选择

针对第i个元素，实际上是有两种选择，一种是与arr[i-1]相连，形成一个最大子数组，一种是自成一派。

4.定义base case

dp[0] = arr[0]

5.思考状态转移方程

6.代码示例

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long[] arr = new long[n];
        for(int i=0;i<n;i++){
            arr[i] = in.nextLong();
        }
       
        //定义dp数组
        long dp[] = new long[n];
        dp[0] = arr[0];
        for(int i=1;i<dp.length;i++){
            dp[i] = Math.max(dp[i-1]+arr[i],arr[i]);
        }
        
        long res = Long.MIN_VALUE;
        for(int i=0;i<dp.length;i++){
            if(dp[i]>res){
                res = dp[i];
            }
        }
        System.out.println(res);
    }
}