一个有N个整数元素的一维数组(A[0],A[1],...,A[n-2],A[n-1])，这个数组当然有很多子数组，那么子数组之和的最大值是什么呢？
【解法一】：我们先明确题意。
1、题目说的子数组是连续的；
2、题目只需要求和，并不需要返回子数组的具体位置；
3、数组的元素是整数，所以数组可能包含有正整数、零、负整数；
举几个例子：
数组：[1, -2, 3, 5, -3, 2]应返回：8
数组：[0, -2, 3, 5, -1, 2]应返回：9
数组：[-9, -2, -3, -5, -3]应返回：-2，这也是最大子数组的和。
这个几个典型的输入能帮助我们测试算法的逻辑。在写具体算法前列出各种可能输入，也可以让应聘者有机会和面试者交流，明确题目的要求。例如：如果数组中全部是负数，怎么办？是返回0，还是最大的负数？ 这是面试和闭卷考试不一样的地方，要抓住机会交流。
了解了题意之后，我们实验最直接的方法，记Sum[i,...,j]为数组A中第i个元素的第j个元素的和(其中0<=i<=j<n)，遍历所有可能的Sum[i,...j]，那么时间复杂度为O(N*N*N)：
1 int MaxSum(int* A, int n) 2 { 3 int maxmum = -INF; 4 int sum; 5 for (int i = 0; i < n; i++) 6 { 7 for (int j = i; j < n; j++) 8 { 9 for (int k = i; k<=j; k++) 10 { 11 sum += A[k]; 12 } 13 if (sum > maxmum) 14 maxmum = sum; 15 } 16 } 17 return maxmum; 18 }
如果注意到Sum[i,...j] = Sum[i,...j-1] + A[j]，则可以将算法中的最后一个for循环省略，避免重复计算，从而使算法得以改进，改进后的算法如下，这时复杂度为O(N*N)：
int MaxSum (int* A, int n) { int maxnum = -INF; int sum; for (int i = 0; i < n; i++) { sum = 0; for (int j = i; j < n; j++) { sum += A[j]; if (sum > maxnum) maxnum = sum; } } return maxnum; }
能继续优化吗？
【解法二】：如果将所给数组(A[0],...,A[n-1])分为长度相等的两段数组(A[0],...,A[n/2-1])和(A[n/2],...A[n-1]),分别求出这两段数组各自的最大子段和，则原数组(A[0],...A[n-1])的最大子段和为以下三种情况的最大值：
1、(A[0],...A[n-1])的最大子段和与(A[0],...,A[n/2-1])的最大子段和相同；
2、(A[0],...A[n-1])的最大子段和与(A[n/2],...A[n-1])的最大子段和相同；
3、(A[0],...A[n-1])的最大子段跨过其中两个元素A[n/2-1]和A[n/2]；
第1和2两种情况事实上是问题规模减半的相同子问题，可以通过递归求得。
至于第3中情况，我们只要找到以A[n/2-1]结尾的和最大的一段数组之和s1 = (A[i],...A[n/2-1])(0 <= i < n/2-1)和以A[n/2]开始和最大的一段数组之和s2 = (A[n/2],...A[j])(n/2 <= j < n)。那么第3种情况的最大值为s1 + s2 = A[i]+...+A[n/2-1]+A[n/2]+...+A[j]，只须要对原数组进行一次遍历即可。
其实这是一种分治算法，每个问题都可分解成为两个问题规模减半的子问题，在加上一次遍历算法。该分治算法的时间复杂度满足典型的分治算法递归式，总的时间复杂度为T(N) = O(N*lgN)。
【解法三】：解法二中的分治算法已经将时间复杂度从O(N*N)降到了O(N*lgN)，应该说是一个不错的改进，但是否还可以进一步讲时间复杂度降低呢？答案是肯定的，从分治算法中得到提示：可以考虑数组的第一个元素A[0]，以及最大的一段数组(A[i],...A[j])跟A[0]之间的关系，有一下几种情况：
1、当0 = i = j时，元素A[0]本身构成和最大的一段；
2、当0 =i < j时，和最大的一段以A[0]开始；
3、当0 < i时，元素A[0]跟和最大的一段没有关系；
从上面三种情况可以看出，可以将一个大问题(N个元素数组)转化为一个较小的问题(n-1个元素的数组)。假设已经知道(A[1],...,A[n-1])中和最大的一段数组之和为All[1],并且已经知道(A[1],...,A[n-1])中包含A[1]的和最大的一段数组为Start[1]。那么，根据上述分析的三种情况，不难看出(A[0],...,A[n-1])中问题的解All[0]是三种情况的最大值max{A[0],A[0]+Start[1],All[1]}。通过这样的分析，可以看出这个问题符合无后效性，可以使用动态规划的方法来解决。
1 int max (int x, int y) // 返回x,y中较大值 2 { 3 return (x > y) ? x : y; 4 } 5 6 int MaxSum (int* A, int n) 7 { 8 Start[n-1] = A[n-1]; 9 All[n-1] = A[n-1]; 10 for (i = n-2; i >= 0; i--) 11 { 12 Start[i] = max(A[i], A[i] + Start[i+1]); // 从数组末尾往前遍历直到数组首 13 All[i] = max(Start[i], All[i+1]); 14 } 15 return All[0]; // 遍历完数组，All[0]中存放着结果 16 }
新方法的时间复杂度已经降到O(N)了。
但一个新的问题出现了：我们额外申请了两个数组All[]、Start[]，能否在空间方面也节省一点呢？
观察这两个递推式：
1 Start[i] = max{A[i], Start[i+1] + A[i]}; 2 All[i] = max{Start[i], All[i+1]};
第一个递推式：Start[i] = max{A[i], Start[i+1] + A[i]}。如果Start[i+1] < 0，则Start[i] = A[i]。而且，在这两个递推式中，其实都只须要用两个变量就可以了。Start[k+1]只有在计算Start[k]时使用，而All[k+1]也只有在计算All[k]时使用。所以程序可以进一步改进一下，只需O(1)的空间就足够了。
1 int max (int x, int y) 2 { 3 return (x > y) ? x : y; 4 } 5 6 int MaxSum (int* A, int n) 7 { // 要做参数检查 8 nStart = A[n-1]; 9 nAll = A[n-1]; 10 for (i = n-2; i >= 0; i--) 11 { 12 nStart = max(A[i], nStart + A[i]); 13 nAll = max(nStart, nAll); 14 } 15 return nAll; 16 }
改进的算法不仅节省了空间，而且只有寥寥几行，却达到了很高的效率。我们还可以换一个写法：
1 int MaxSum (int* A, int n) 2 { // 要做参数检查 3 nStart = A[n-1]; 4 nAll = A[n-1]; 5 for (i = n-2; i >= 0; i--) 6 { 7 if (nStart < 0) 8 nStart = 0; // 检查全部是负数，如何？ 9 nStart += A[i]; 10 if (nStart > nAll) 11 nAll = nStart; 12 } 13 return nAll; 14 }
为什么火狐没有一个独立的扩展开发工具啊！！！（估计有，但是我找不到……哪位大神知道的麻烦告诉我，谢谢啦）
不断的修改程序、压缩、修改后缀名、安装、重启……
调试一次起码要10秒钟……好坑爹……算了，吐槽完毕，开始今天的笔记……
------------------------------ 我万恶的分割线 -------------------------------------
一、配置程序
这里我就不再解释火狐扩展中每个文件的作用和功能了，想了解的请移步《黄聪：一、如何创建一个状态栏扩展（火狐插件扩展开发教程）》
这次的扩展我实现的功能是通过新浪开放接口获取当前IP对应的地址信息，并显示在右下角的状态栏上。刚开始的配置如下：
- 在任意一个文件夹创建一个文件夹，命名hcip。
- 在hcip文件夹下面创建一个文件夹，命名chrome。
- 在hcip文件夹下面创建两个文件，分别为install.rdf、chrome.manifest
- 在chrome文件夹下面创建一个文件夹，命名为content。
- 在content文件夹下面创建一个文件，命名为hcip.xul。
- 在content文件夹下面创建一个文件，命名为hcip.js。
- 还是那句话，每个文件要为utf-8格式，以免有中文出错。
最后得到：
二、配置install.rdf文件
不多做解释啦，内容如下：
install.rdf三、配置chrome.manifest文件
content hcip chrome/content/
# Firefox
overlay chrome://browser/content/browser.xul chrome://hcip/content/hcip.xul
四、配置hcip.xul文件
<?xml version="1.0" encoding="UTF-8"?> <!DOCTYPE overlay > <overlay id="stockwatcher-overlay" xmlns="http://www.mozilla.org/keymaster/gatekeeper/there.is.only.xul"> <!-- 引用我自己写的js文件，用来实现远程获取IP信息的功能 --> <script type="application/x-javascript" src="chrome://hcip/content/hcip.js"/> <!-- Firefox --> <statusbar id="status-bar"> <statusbarpanel id="hcip" label="点我获取地址" tooltiptext="" onclick="HCIP.getdz()" /> </statusbar> </overlay>
五、配置hcip.js文件
var HCIP = { startup: function() { this.getdz(); }, getdz: function() { var samplePanel = document.getElementById('hcip'); samplePanel.label = "加载中，稍等......"; var httpRequest = null; var fullUrl = "http://int.dpool.sina.com.cn/iplookup/iplookup.php?format=js"; function infoReceived() { var samplePanel = document.getElementById('hcip'); eval( httpRequest.responseText ); //获取地址信息 var dz = remote_ip_info.country + " > " + remote_ip_info.province + " > " + remote_ip_info.city; //显示在状态栏上面 samplePanel.label = dz; samplePanel.tooltipText = dz; } httpRequest = new XMLHttpRequest(); //从新浪那边获取IP信息 httpRequest.open("GET", fullUrl, true); //获取成功了，调用infoReceived方法 httpRequest.onload = infoReceived; httpRequest.send(null); } } // 初始化 window.addEventListener("load", function(e) { HCIP.startup(); }, false);
六、打包程序、安装运行
- 返回到hcip文件夹，全选所有文件，然后压缩成ZIP格式。
- 修改hcip.zip的后缀名为xpi，最后得到hcip.xpi文件。
- 把hcip.xpi文件拖拽到火狐浏览器中，出现提示安装的界面，点击安装，然后重启火狐。
- 看火狐右下角的状态栏，就有地址信息了。
案例下载点后面的文件》》firefox-hcip.zip