编程之美连载——连续子数组和的最大值

问题

给定一整数数组，求连续的子数组和的最大值，例如：
1， -2， 3， 5， -3， 2 最大值为8
0， -2， 3， 5， -1， 2 最大值为9

分析

《编程之美》中给出的算法很精炼，然而解释却比较复杂，如果从“分级组合”的角度去理解要方便很多。

解法

设置两个整数变量：cur 和sum，从给定数组中依次取出所有元素，加到cur 上去，当cur<0 时候重置cur。sum 记录cur 出现过的最大值：

var cur = array[0];

var sum = cur;

for (int i = 1; i < array.Length; i++)

{

cur = cur < 0 ? array[ i ] : cur + array[ i ];

if (sum < cur) sum = cur;

}

return sum;

扩展问题二解法

如果要求得到最大和的连续子数组的起始位置，那么通过以上思路就更加容易写出代码：

int start1 = 0, start2 = 0, end = 0;

var cur = array[0];

var sum = cur;

for (int i = 1; i < array.Length; i++)

{

    if (cur < 0)

    {

        cur = array[ i ];

        start2 = i;

    }

    else cur += array[ i ];

    if (sum < cur)

    {

        sum = cur;

        end = i;

        start1 = start2;

    }

}

//返回 [start1, end]

本例中，我们用start1，start2 来记录起始位置，end 来记录终止位置。start2 相当于“工作变量”，start1 保存历史最大和连续子数组的起始位置。

扩展问题一解法

如果给定的是数组是首尾相连的循环数组，如何求解？首先设计一个函数，求解给定数组中，从from 开始的，最多到to 结束的最大和连续子数组的末尾位置，思路和前面解法类似。

int MaxSum_Position(int[] array, int from, int to)

{

    int step = Math.Sign(to - from);

    int end = from;

    var cur = array[from];

    var sum = cur;

    for (int i = from + step; i != to + step; i += step)

    {

        cur += array[ i ];

        if (sum < cur)

        {

            sum = cur;

            end = i;

        }

    }

    return end;

}

有了这个函数以后，可以将循环数组中的问题分成两种情况：一种是连续子数组跨越了0 位置的，一种是没有跨越的：

int sum1 = MaxSum(array);//不跨越0 位置的最大和

int i = MaxSum_Position(array, 0, array.Length - 1);

int j = MaxSum_Position(array, array.Length - 1, 0);

int sum2 = 0;

if (i > j) j = i + 1;

for (int k = 0; k < array.Length; k++)

{

sum2 += array[ k ];

if (k == i) k = j - 1; //跳过中间空缺部分

}

return Math.Max(sum1, sum2);