AImager

最大连续子串和是一个比较经典的问题，不在于它的难度，而在于它衍生出来的多种解题思路，并且每种思路都极具代表性。

问题描述

有一实数序列，定义为 $a_1,a_2,a_3…,a_n$ ，寻找一段连续子序列 $a_i,a_{i+1}…,a_j$ ，其中i<=j，i>=1，j<=n，使得该子序列的和最大。

DP

在优化算法的过程中，一个常有成效的思路DP，即抽离子问题，然后保存可供复用的子问题解，避免重复计算。在最大连续子串和的问题中， $sum(a_i,…,a_{j+1}) = sum(a_i,…,a_j) + a_{j+1}$ ，因此只要优先算出了 $sum(a_i,…,a_{j-1})$ 并保存下来，那总是可以在O(1)时间复杂度下得到 $sum(a_i,…,a_j)$ 这个子问题的解，从而整体时间复杂度降到了 $O(n^2)$ 。

分治

复杂度 $O(nlgn)$

贪心

DP可以避免重复计算，但是无法避免不必要的计算，所以考虑有没有办法只循环一次不用回溯就得到结果？嗯，贪心！

假设 $a_i,…,a_j$ 为最大子序列，显然对 $ sum(a_i,…,a_k), i<=k<=j$ ，其值总是大于0，如果小于等于0，则 $sum(a_{k+1},…,a_j)$ 显然就大于等于 $sum(a_i,…,a_j)$ ，因此可以按下面的流程来计算这个结果。

1. 设置 $tempSum=0$ ， $maxSum=a_1$ ， $k=1$ 。
2. 计算 $tempSum = tempSum + a_k$
3. 若 $tempSum >= maxSum$ ，设置 $tempSum = maxSum$ 。
4. 若 $tempSum <= 0$ ，设置tempSum = 0。
5. 设置 $k=k+1$ ，若k大于序列长度n，结束；否则执行1。

以上流程结束后得到的maxSum即最大连续子串和，但是有以下问题需要注意。

• 流程里面没有记录起始位置，如果要记录，需加上一个标志位
• 若存在多个分散的子序列和均为最大值，则上述流程计算的是最后一个，若把第3步的>=改成>，则计算的是第一个
• 若存在两个子序列和均为最大值，且相互为父子关系，则上述流程计算的是较短的一个，若把第4步<=改成<，则计算的是较长的一个

下面给出贪心的代码，DP和枚举的就省了。

$arr = [-1,199,-4,40,-5];
$tempSum = 0;
$maxSum = $arr[0];
$maxStart = 0;
$maxEnd = 0;

$switch = 0;        // 用来表示截断后是否有设置maxStart，1表示没设置

foreach($arr as $index => $val) {
    $tempSum += $val;
    if($tempSum >= $maxSum) {
        if ($switch == 1) {
            $maxStart = $tempMaxStart;
            $switch = 0;
        }
        $maxEnd = $index;
        $maxSum = $tempSum;
    }

    if ($tempSum <= 0) {
        $tempSum = 0;
        $tempMaxStart = $index + 1;
        $switch = 1;
    }
}

echo "\n maxSum : " . $maxSum;
echo "\n maxStart ~ maxEnd : " . $maxStart . " ~ " . $maxEnd;