这道题最容易想到的解决方案是O(N2)时间复杂度的解决方案，建立一个二维数组，记录所有以ai开头aj结尾的子数组的和，并找出他们的最大值。可能是牛客网测试数据数据量不够大，这个解决方案的代码也能AC，居然没有超时。因为方案太简单了，这个方案的代码就不贴上来了。
    因为之前一直没搞懂动态规划，所有看别人的题解，一看到有DP，前缀这样的字眼，心里就有点发毛，就觉得问题很难，我没学过，不会......后面经过了一段时间的心理调整后(时间有点长，看了下提交时间，居然过了一个月了😆），发现其实不用系统地学习DP相关的知识，只要认真分析这个问题，也能找到解决方案。
    我尽量用通俗易懂的方式展示自己的解题思路，希望能帮助到大家，同时也提升我自己。
    我们先来看题目的需求：

        输入一个整形数组（可能有正数和负数），求数组中连续子数组（最少有一个元素）的最大和。要求时间复杂度为O(n)。

    最开始，是自己思维定式了，因为受文章开头提到的时间复杂度O(N2)的傻白甜解决方案的影响，脑海里一直的理念就是，要想求连续子数组最大和就必须知道这个连续子数组的开头和结尾，就必须要遍历所有ai开头aj结尾的情况，所以O(N2)仿佛是个死结。前几天看了一个斐波那契数列扩展的题解，居然发现一道水题，如果仔细分析，居然也能折射出智慧的光芒。
    之前我们其实的方法是遍历以ai开头的连续子数组，现在我们来转换下思路，因为题目只需要我们求出连续子数组最大和就可以了，并不需要我们找出连续子数组的开头和结尾，所以我们干脆这样想，让我们忘记开头吧，只记得结尾。我只需要记住以aj为末尾元素的连续子数组的最大和，则当我们算aj+1为末尾元素的连续子数组的最大和的时候，我们只需要考虑两种情况：
    设以aj为末尾元素的连续子数组的最大和为sumj,
    如果sumj<0,则aj+1+sumj < aj+1,那么sumj+1=aj+1
    如果sumj>=0，则aj+1+sumj >= aj+1,那么sumj+1=aj+1+sumj

    进一步解释下上面的结论。我们先看一种极端情况，数组只有一个元素a1，那么连续子数组最大和很简单，肯定就是a1.也就是说以a1结尾的连续子数组最大和就是a1，即sum1=a1.
    好，咱们接着继续往下走，如果数组有两个元素，我们指定以a1结尾的连续子数组最大和就是sum1，那么以a2结尾的连续子数组最大和sum2是多少呢？
    我们可以确定，以a2结尾的连续子数组最大和只会是两种子数组情况，一种就是a2跟a1拼在一起，组成[a1，a2]数组,一种就是放弃a1，[a2]自成一个子数组。
    也就是比较a1+a2与a2的大小
    根据我们上面粗体字部分的结论，
    如果sum1<0，则sum2=a2
    如果sum2>=0,则sum2=a2+sum1
    如果数组有3个元素，a1，a2，a3，那么以a3结尾的连续子数组，有两类：一类是子数组中有a2的，有[a1，a2，a3]；[a2，a3];一类是子数组中没有a2的，这样就只有[a3],因为前提是连续子数组，所以不存在[a1,a3]这样的情况。
    对于有a2的，[a1，a2，a3]；[a2，a3]这种情况，哪个子数组的和最大呢，就是比较a1+a2+a3与a2+a3的大小，去掉两边的a3，也就是比a1+a2与a2的大小，是不是发现又转换成上一个以a2结尾的连续子数组最大和的问题了，
    而我们上一步已经计算出了以a2结尾的连续子数组最大和为sum2，那么
    如果sum2<0，sum2+a3([a1，a2，a3]；[a2，a3]和的较大值）<a3（子数组中没有a2的，这样就只有[a3]）,则sum3=a3
    如果sum2>=0,则sum3=a3+sum2
    ......
    如果sumn-1<0,则an+sumn-1 < an,那么sumn=an
    如果sumn-1>=0，则an+sumn-1 >= an,那么sumn=an+sumn-1
    这样我们就能算出sum1，sum2，sum3......sumn，
    那么，sum1到sumn中的最大值，就是该数组的连续子数组最大和了。

    如果上面看得还是头晕的话，我再结合测试用例来讲一下：
    数组为：[1,-2,3,10,-4,7,2,-5]
    以a1结尾的连续子数组只有一种情况[a1],即[1],那么sum1=1；
    以a2结尾的连续子数组有两类情况，带a1的：[a1,a2],即[1,-2],不带a1的，[a2],即[-2],对应的数组和为-1，-2，那么sum2=-1;
    以a3结尾的连续子数组也有两类情况，带a2的：[a1,a2,a3],[a2,a3]，即[1,-2,3],[-2,3],不带a2的，[a3]，即[3].从上面我们已经知道了，以a2结尾的连续子数组最大和为-1，也就是说最好的情况都是给负数，那么聪明的a3，肯定会果断抛弃这个坑队友，因为跟它相加，结果只会更差，那么sum3就是a3抛弃前面的坑队友,自立门户,那么sum3=3.
    同样，以a4结尾的连续子数组，对于前面的元素能组成多少个排列组合能跟它凑成一个连续子数组已经不感兴趣了，它只关注前面计算出来的sum3是否是正数，如果是正数，就果断跟前面组成sum3的那个连续子数组结合在一起，把事业做大做强，如果不是正数，就果断抛弃，然后自立门户。这里a4发现sum3=3，果断拉拢，所以sum4=10+3=13.
    同理可以知道sum5=9，sum6=16，sum7=18，sum8=13,那么sum1到sum8中的最大值为sum7=18，所以输出结果18.    
    好，大道理讲完了，下面贴代码开干： 
package com.igeekspace;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        while (scanner.hasNextInt()) {
            int n;
            n = scanner.nextInt();

            //存储数组元素
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = scanner.nextInt();
            }

            //记录以aj为末尾元素的连续子数组的最大和
            int[] maxSums = new int[n];
            maxSums[0] = nums[0];

            int max = maxSums[0];
            for (int i = 1; i < n; i++) {
                maxSums[i] = maxSums[i - 1] < 0 ? nums[i] : maxSums[i - 1] + nums[i];
                max = Math.max(maxSums[i], max);
            }

            System.out.println(max);
        }
    }
}

    本人致力于编写通俗易懂的解题报告，如果对上面有任何没看明白的地方，请直接留言回复。我会尽我所能完善解题报告。
    我建立了一个git仓库专门存放代码，以及测试用例等资料，仓库地址：https://github.com/S-Knight/nowcoder
    如果你觉得本文对您有帮助，记得给我点赞哦，你们的点赞是我持续更新的动力。