傻瓜笔记——连续子数组最大和的三种解法（实则是两种解法）

问题描述：给一个若干长度的整数数组，求该数组中连续的最大值。

例如： Z = ｛1，-2，3，10，-4，7，2，-5｝，那么结果输出的就是 18 = ｛3，10，-4，7，2｝

第一种：暴力破解（时间复杂度O（n²））

 1         public static int DP()
 2         {
 3             for (int i = 0; i < v.Length; ++i)
 4             {
 5                 for (int j = i; j < v.Length; ++j)
 6                 {
 7                     unMax = unMax + v[j];
 8                     max = Math.Max(max, unMax);
 9                     Console.WriteLine("第" + i + "次" + ":" + unMax + " + " + max);
10                 }
11                 unMax = 0;
12             }
13             return max;
14         }

其中unMax是临时最大值，这种方法不多BB

第二种：动态规划（时间复杂度O（n））

状态转移方程： dp = max｛dp[i-1]+arr[i],arr[i]｝

public static int getSum2()
        {
            for(int i = 0;i<v.Length;++i)
            {
                unMax = Math.Max(unMax + v[i], v[i]);
                max = Math.Max(unMax, max);
            }
            return max;
        }

代码解读：放到和第三种一起说！

第三种：（不知道叫什么）

看问题的角度：假设DP[] 是一个集合，同时也是Z=｛｝的一个连续子数组，用来记录最终结果（别人称这个是框集）。

从第一个元素开始遍历，一直往后推，当前 i 个元素的和小于0的时候那么框集清空，否则将该元素加入框集，直至整个数组遍历完毕。

 1  public static int getSum()
 2         {
 3             for(int i = 0;i<v.Length;++i)
 4             {
 5                 unMax = unMax + v[i];            
 6                 if (max < unMax)
 7                 {
 8                     max = unMax;
 9                 }
10                 if (unMax < 0)            // 如果框集总和小于0  则将该框集前移，意味着，此次的元素不适合加入到该框集,需要将框集元素前移保留上一次的结果，再下次的比较中则相当于一个新的框集
11                 {
12                     unMax = 0;
13                 }
14             }
15             return max;
16         }

代码解读：其实方法二和方法三的思想是一样的，只是看待问题的角度可能略有偏差，而且方法三更易于理解。所以现在就方法三来解释去解释方法二：假设现在有一个无限长的整数数组Z=｛｝，真的很长很长，让你求其中最大连续和，那么肯定从第一个元素开始遍历，那么现在假设D=｛｝是最大连续和的数组，所以随着遍历下去，D就会一直从Z中挑选元素加入到D中，想象一下，从Z中加入了第一个...第二个...第三个...元素，期间所求和一直是非负数，但是直到第 i 个的时候，总和小于0了，那么意味着加入该数组使得原先的 D 变成了一个没点用的数组，因为无论后面的数字再大，哪怕是正无穷，都已经不是Z=｛｝数组的最大连续和了，那么就需要将 D 数组的长度前移一位，即不要当前这个导致 D 总和小于0的元素，但是如果不要的话，D 就不是连续的了，所以此时将 D 看成是一个新的集合，当中的元素是空的，没有任何元素是个空集，那么D就可以继续的从下一个元素开始遍历 Z 了，直到又碰到了使 D 总和小于0的元素（如果该元素使 D 小于那么该元素必定是负数，这很好理解），在遍历期间，当 D 每加入一个新元素的时候都会和当前保存的Max进行比较，所以当 Z 遍历完成的时候，得到的Max就是 Z =｛｝数组的连续最大和。

综上所述，其实方法三和方法二是一样的，就连判断的步骤都是一样的，只是方法二写起来方便，方法三便于理解。

PS：方法三是参考geeksforgeeks，Largest Sum Contiguous Subarray 网站的

傻瓜笔记——连续子数组最大和的三种解法（实则是两种解法）

相关推荐