最大数组问题

        一维最大子数组和问题，即给定一个数组，在它所有的连续子数组的和中，求最大的那个和。“最大子数组和”是一个很好的IT面试考题，在《编程之美》一书中同时阐述了一维数组和二维数组的讨论。本篇博客将会更加细致的讨论一维部分。

　　一. 最直观的 O(n³) 解法

　　在课上看到这个问题，当然最直观的解决办法即穷举。我们通过对子数组的起点和重点进行二层循环，计算每一个子数组的和，取其最大值，这样当然能够解决。但是作为一种O(n³）的解法，显然是低效率的。

　　二. 进一步思考——O(n²)解法

　　为增加程序效率，在接触过的算法中，我们想到或许动态规划能够被运用。动态规划的思想是将前一步的结果存储起来并在后续的步骤中直接使用，减少重复性劳动。因为a[1,10]这样的子数组可以拆解为a[1,9] + a[10], 所以我们可以思考一下如何运用动态规划来增加效率。

　　核心问题是，如何运用动态规划，在哪里用。因为是求和，动态规划就被用来存储已经求和的子数组和，供包含此子数组的子数组的求和来使用。那么，我们仅使用上述O(n³)算法的两层循环，求和过程就简化为线性的复杂度，因此此算法的时间复杂度能被降低为O(n²)。

　　三. 惊艳！——O(n) 解法

　　O(n)算法是我在博客上看到的。看到竟然有O（n）算法，不禁佩服起人类的智慧... 不过，尝试不看解答，我们先想想，是在哪一部分把数量级降低了1呢？要达到O(n)的时间复杂度，必须将循环减至1层。这是容易想到的。问题是：循环减到1层，又如何处理每一层、并且得到最大子数组和呢？下面我们来看看方法：

　　对于一个数组a[1]...a[L-1]，假设我们已经知道其最大子数组和为max_former。当数组增加一个元素a[L]在结尾，那么新数组和最大的子数组要么包含a[L+1]在末尾，要么没有a[L+1]，仍保持原先的子数组不变。用max_updated表示以a[L+1]结尾的最大子数组的和，则增加1个元素后新数组的max_former新=max(max_updated, max_former旧).

　　在max_former旧 已知情况下（动态规划存储的中间步骤）下面只需求max_updated。max_updated旧 表示以a[L-1]结束的最大子数组和。以显然增加一个元素后，max_updated新=max(max_updated旧+a[L+1], a[L+1])。

　　上面两段的思考，我们得到：

#define NENIL -10000000 //定义哨兵大小

template <class T>
void sum_max(T myAarry[],int count,int& inleft,int& inright,T& Maxsum)
{
    T max_sum=NENIL; //设定最大数组的初值
    T update_sum=NENIL; //设定不断更新的初值
    int left=0; //设定最大数组初始范围
    int right=0;

    for(int i=0;i<count;i++)
    {
        bool bcompare=false;
        if(myAarry[i]+update_sum>myAarry[i])
        {
            update_sum=myAarry[i]+update_sum;
            bcompare=true;
        }
        else
        {
            update_sum=myAarry[i];
        }
        if(max_sum<update_sum)
        {
            max_sum=update_sum;
            if(bcompare)
            {
                right=i;
            }
            else
            {
                left=right=i;
            }
        }
    }
    inleft=left;
    inright=right;
    Maxsum=max_sum;
}

前面讲到的三个算法，可以理解为循序渐进的优化过程。O(n³)最为直观，当我们尝试使用动态规划存储中间步骤求得的和时，我们将O(n³) 简化为(n²)。至于O(n)算法，就是在动态规划存储上一步结果的前提下，只对子数组末尾元素进行一层循环。这里面运用到了一个巧妙的思维避开了O(n²)算法的两层循环。