算法-子数组连续序列最大和其时间复杂度如何从O(n^3)到O(n)

求数组的连续子数组和的最大值。如何做到时间复杂度从O(n^3)，O(n^2)，再到O(n)呢？ 这中间我们应该做哪些思考使复杂度逐渐变小呢？这些思想怎么能应用到我们的开发中呢？ 下面分别看下这几个版本的代码实现。

版本一
时间复杂度 O(n^3)。穷尽法

        //nums = {5, -3, 4, 9, -6, 5, 1}

//O(n^3)
        public int MaxSubArraySum1(int[] nums)
        {
if(nums.Length==0)
return 0;
int max = nums[0];
int i, j, k;
for (i = 0; i < nums.Length; i++)
            {
for (j = i; j < nums.Length; j++)
                {
int sumij = 0;
for (k = i; k <= j; k++)
                    {
                        sumij += nums[k];                        
                    }
max = Math.Max(sumij, max);
                }
            }
return max;
        }

版本二
时间复杂度 O(n^2)。利用以下等式：
sum[i,j] = sum[i,j-1]+nums[j];

 //O(n^2)

 public int MaxSubArraySum2(int[] nums)
 {
if (nums.Length == 0)
return 0;
int max = nums[0];
int i, j, k;
for (i = 0; i < nums.Length; i++) 
 {
int sumij = 0;

for (j = i; j < nums.Length; j++)//保持 i 不变
 {
 sumij += nums[j];
max = Math.Max(sumij, max);
 }

 }
return max;
 }

版本三
时间复杂度 O(n^2)。 通过累加数组与上一版本近似。

        //O(n^2)
//累加数组
//sum[i:j] = sum[j] - sum[i-1]
//O(n^2)
//原理：sum[i,j] = sum[i,j-1]+nums[j];
public int MaxSubArraySum3(int[] nums)
        {
if (nums.Length == 0)
return 0;
int max = nums[0];
int i, j, k;
int[] accu = new int[nums.Length];
            accumulator(nums,accu);
for (i = 0; i < nums.Length; i++)
            {
int sumij = 0;
for (j = i; j < nums.Length; j++)//保持 i 不变
                {
                    sumij = i==0? accu[j]:accu[j] - accu[i - 1];
                    max = Math.Max(sumij, max);
                }
            }
return max;
        }

private void accumulator(int[] nums, int[] accu)
        {
            accu[0] = nums[0];
for (int i = 1; i < nums.Length; i++)
            {
                accu[i] = accu[i - 1] + nums[i];
            }
        }

版本三
线性复杂度O(n)。此算法是卡内基梅隆大学的 Kadane 教授发现的。

        //获取子数组的最大和
public int MaxSubArraySum5(int[] nums)
        {
int maxSofar = nums[0];
int maxCur = nums[0];
for(int i=1; i<nums.Length;i++)
            {              
                maxCur = Math.Max(nums[i], nums[i] + maxCur);
                maxSofar = Math.Max(maxCur, maxSofar);
            }
return maxSofar;
        }