【美团笔试】最大子段和

题目二
题目描述
最大子段和是一个经典问题，即对于一个数组找出其和最大的子数组。
现在允许你在求解该问题之前翻转这个数组的连续一段（如翻转{1,2,3,4,5,6}的第三个到第五个元素组成的子数组得到的是{1,2,5,4,3,6}），则翻转后该数组的最大子段和最大能达到多少？

输入描述
第一行有一个正整数n(1<=n<=100000)，代表数组长度。
第二行有n个空格隔开的整数(-1000<=ai<=1000)，代表给出数组。

输出描述
输出一个整数，代表若允许你翻转一个子数组 ，则翻转后所得数组的最大子段和最大能到多少。

样例输入

6
-1 3 -5 2 -1 3
样例输出

7

相信最大子段和，在座的各位应该都会吧，这里的题目说，可以反转一个子数组，求翻转之后的最大字段和，难度瞬间就上来了，写题的时候根本没思路，一遇到翻转啊，首尾链接啊，我就完全没思路了，本题使用动态规划 + 前缀和求解。

看了大佬的题解，简直太妙啦，首先，维护 a 为原数组，维护一个数组 sum 为前缀和数组，一个数组 maxNow 为当前子段的和，维护 maxValue 为最大字段和，ans 为最后的结果，首先，求出前缀和，sum[i] 的含义是：a 数组前 i 项元素的和，那定义一个变量 s，为前 i 个和，如果 s 小于 0，就让 s 重新为 0，这样 s 和 maxNow 就能算出，当前元素的大于零总和

定义 maxValue 数组，由于 sum[i] 为前 i 元素的和，maxNow[i] 为前 i 元素大于 0 的和，让后者减去前者，在 maxValue 的时候再加回来，就可算出翻转后的最大子段和

（思想就是这么个思想，但是实践肯定还是不会，再练习把，动态规划的题目还是难点！）

package com.company;

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] sum = new int[n + 1];
        int[] a = new int[n + 1];
        int[] maxNow = new int[n + 1];
        int[] maxValue = new int[n + 1];
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
            sum[i] = sum[i - 1] + a[i];
        }
        int s = 0;
        for (int i = 1; i <= n; i++) {
            s += a[i];
            if (s < 0) {
                s = 0;
            }
            maxNow[i] = Math.max(maxNow[i - 1], s);
            maxValue[i] = Math.max(maxValue[i - 1], maxNow[i] - sum[i]);
            ans = Math.max(ans, maxValue[i - 1] + sum[i]);
        }
        System.out.println(ans);
    }


}