寻找最大子列表

航海日志

2018-05-14

https://leetcode.com/problems/maximum-subarray/

Description

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

给定一个数字列表，找到其中子列表内的值相加能得到的最大的数字

Example

1
2
3

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Answer

def maxSubArray(A):
    if not A:
        return 0

    curSum = maxSum = A[0]
    for num in A[1:]:
        curSum = max(num, curSum + num)
        maxSum = max(maxSum, curSum)

    return maxSum

Thinking

Kadane算法：

中文维基解释: Kadane算法扫描一次整个数列的所有数值，在每一个扫描点计算以该点数值为结束点的子数列的最大和（正数和）。该子数列由两部分组成：以前一个位置为结束点的最大子数列、该位置的数值。因为该算法用到了“最佳子结构”（以每个位置为终点的最大子数列都是基于其前一位置的最大子数列计算得出），该算法可看成动态规划的一个例子。

初始化当前最大值和总共的最大值都是【零号位】

用【index 1】与【index0 + index1】相比

【index1】大的话，当前最子列表就是【index1】，再用【index2】和【index1 + index2】相比

【index0 + index1】大的话，当前最大子列表就是【index0 + index1】，再用【index2】和 i【ndex0 + index1 + index2】相比

以此类推

每次比较的都是当前位置之前最大的子列表（可能是前面一部分的想加之和或者是当前位置的数）与当前最大子列表值总和加下一个值的和作比较

Fixme

Reference 3中的二分法解法