求数组的子数组之和的最大值
一个有N个整数元素的一维数组(A[0],A[1],...,A[n-2],A[n-1])，这个数组当然有很多子数组，那么子数组之和的最大值是什么呢？
【解法一】：我们先明确题意。
1、题目说的子数组是连续的；
2、题目只需要求和，并不需要返回子数组的具体位置；
3、数组的元素是整数，所以数组可能包含有正整数、零、负整数；
举几个例子：
数组：[-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 }
分类: 算法分析
标签: 面试 , 子数组之和的最大值
黄聪：二、如何通过URL获取其他网页源代码内容（火狐插件扩展开发教程）
为什么火狐没有一个独立的扩展开发工具啊！！！（估计有，但是我找不到……哪位大神知道的麻烦告诉我，谢谢啦）
不断的修改程序、压缩、修改后缀名、安装、重启……
调试一次起码要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://HdhCmsTestmozilla.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测试数据.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
作者： Leo_wl
出处： http://HdhCmsTestcnblogs测试数据/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息