寻找连续最大和子数组

剑指offer面试题系列

题目：输入一个整型数组，数组里有正数也有负数，数组中一个或者连续的多个整数组成一个子数组，求所有子数组中的和的最大值。要求时间复杂度为O(n)。

Analyze

刚拿到题的时候，花了大概五分钟的时间，连思路带实现三下五除二搞定，不亦快哉！

但是，做了这么多的剑指offer的题，深感不安，有这么容易么？仔细再一想，是错误的。

题目要求的是寻找连续的子数组，我直接按照从0下标开始的连续子数组思考了。审题不细致啊！

于是推到重来，这一重来就再没做出来直到看了剑指offer上的思路提示，汗！

我在剑指offer的思路上，添加了我自己的理解和实现。现说明如下：

关于 Sum， 声明三个变量，preSum保存上一轮循环的元素之和，curSum保存当前循环的数组和，maxSum保存最大的和。startIndex保存子数组开始下标，endIndex保存子数组结束下标。

如果preSum小于0，则可以想到，前面的所有元素只能起到一种“负的效应”，果断抛弃前面的序列，但是要保存前面的序列之和。

如果preSum大于0，则继续累加，如果当前累加和大于maxSum，则更新之，同时更新endIndex。

下面是这个代码流程的表格表示：

Code

package com.study;

/*连续整形子数组的最大和*/
public class Solution18 {
    public static int[] GetSum(int[] arr) {
        int startIndex = 0;
        int endIndex = 0;
        int preSum = 0;
        int CurSum = 0;
        int MaxSum = 0;

        for (int i = 0; i < arr.length; i++) {
            if (preSum < 0) {
                startIndex = endIndex = i;
                CurSum = arr[i];
            } else {
                CurSum += arr[i];
            }
            if (CurSum > MaxSum) {
                MaxSum = CurSum;
                endIndex = i;
            }
            preSum = CurSum;
        }

        int[] subArr = new int[endIndex - startIndex + 1];
        for (int k = startIndex, j = 0; k <= endIndex; k++) {
            subArr[j++] = arr[k];
        }
        return subArr;
    }

    public static void main(String[] args) {
        int[] arr1 = { 1, -2, 3, 10, -4, 7, 2, -5 };
        int[] arr = { -1, -2, -3, -4, 5, 8, -6, 9 };
        int[] subarr = GetSum(arr);
        for (int k = 0; k < subarr.length; k++) {
            System.out.print(subarr[k] + " ");
        }
    }
}

Summary

还是没有掌握这种用表格表示的方法啊，通过这道题，更加明白了表格表示法在变量迭代更新的流程中起到的作用。这种方法最能看出迭代变量之间的关系，有助于快速理清思路。

今后，要多用之，熟练用之。