题解 | #连续子数组最大和(ACM版本)#

我不怎么会动态规划，只能这样了、、、

import java.util.*;

public class Main {
    /*
     
    */
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] arr = new long[n];
        int j = 0;
        while(j++ < n){
            arr[j-1] = sc.nextLong();
        }
        int start = 0,end = 0;
        long sum = 0;
        int maxSum = 0;
        long[] tmp = new long[]{sum,start,end}; // 始终存放最大和，开始，结束索引
        
        for(int i = 0; i < arr.length; i++){  
            // 前面数之和加上当前数结果 小于0，则比较前面数之和与最大和，将最大的和存起来，并且从下一个数字开始计算
            if(sum + arr[i] < 0){
                if (sum > tmp[0]){
                    tmp[0] = sum;
                    tmp[1] = start;
                    tmp[2] = end;
                }
                start = end = i+1;
                sum = 0;
            } else { 
                sum += arr[i];
                end = i+1;
                // 比较前面数之和与最大和，将最大的和存起来
                if (sum > tmp[0]){
                    tmp[0] = sum;
                    tmp[1] = start;
                    tmp[2] = end;
                }
            }
            
        }
        // 处理全是负数的情况
        if (sum <= 0){
            Arrays.sort(arr);
            System.out.println(arr[arr.length-1]);
            return;
        }
        // 最后一次也需要处理比较
        if(sum > tmp[0]){
            tmp[0] = sum;
            tmp[1] = start;
            tmp[2] = end;
        }
        System.out.println(tmp[0]);
    }
}