连续子数组的最大和.md

题目描述

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

测试用例

• 功能测试（输入的数组汇中有正数也有负数；输入的数组中全是正数；输入的数组中全是负数）
• 特殊输入测试（表示数组的指针为空指针）

题目考点

• 考察应聘者对时间复杂度的理解。这道题如果应聘者给出时间复杂度为O(n2)甚至O(n3)的算法，则是不能通过面试的。
• 考察应聘者对动态规划的理解。
• 考察应聘者思维的全面性。能否合理地处理无效的输入。

解题思路

动态规划思想

我们用函数f(i)来表示以第i个数字结尾的子数组的最大和，那么我们需要求出max[f(i)],其中求出max[f(i)],其中0<=i<n,我们可以用如下递归公式求f(i)：

f(i) = array[i]              i = 0 或者 f(i) <= 0
f(i) = f(i-1) + array[i]     i > 0 f(i) > 0

如果我们用一个数组来表示f(i)，那么最后我们又要排序，所以又在无形之见加入了时间复杂度，所以在进行上述过程中就需要加入比较逻辑，当上诉过程完成之后，最大值也得到了。

自己解题

/**
 * 连续子数组的最大和
 *
 * @Author rex
 * 2018/8/25
 */
public class Solution {
    /**
     * 找规律解法(思想还是动态规划的)
     * @param array
     * @return
     */
    public int findGreatestSumOfSubArray(int[] array) {

        if (array == null || array.length == 0) {
            return 0;
        }
        int max = array[0];

        int curMax = max;
        for (int i = 1; i < array.length; i++) {

            if (curMax <= 0) {
                curMax = array[i];

            } else {
                curMax += array[i];

            }
            if (curMax > max) {
                max = curMax;
            }

        }
        return max;
    }
}

20ms，还是很快的！！

参考解题

见自己解题。

补充

虽然通常我们用递归的方式来分析动态规划的问题，但最终都会基于循环去编码。