动态规划（牛客网）

看到最值题目分析一下是否存在最优子结构，是否有重复子问题。
这题和前面一题连续子数组最大和有点相似，不过得多考虑一种情况：最大和可能刚好在环处。
这种情况可以通过在整体数组之和 减去 最小值和。

那么定义状态转移方程需要维护两个dp数组，仔细分析可以发现转移时值往往之和前一个有关，那么是可以进行空间压缩的，使用一个变量即可。

dpmax = arr[i] + Math.max(dpmax, 0);
dpmin = arr[i] + Math.min(dpmin, 0);

状态转移方程有了只需考虑一下base case，这题就差不多了

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[ n];
        for(int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int dpmax = arr[0];
        int dpmin = arr[0];
        int maxval = arr[0];
        int minval = arr[0];
        int sum = arr[0];
        for(int i = 1; i < n; i++) {
            dpmax = arr[i] + Math.max(dpmax, 0);
            maxval = Math.max(maxval, dpmax);
            dpmin = arr[i] + Math.min(dpmin, 0);
            minval = Math.min(minval, dpmin);
            sum += arr[i];
        }
        if(maxval > 0) {
            System.out.println(Math.max(maxval, sum - minval));
        }
        else {
             System.out.println(maxval);
        }
       
    }