求子數(shù)組最大和的解決方法詳解
更新時(shí)間：2013年05月23日 17:43:07 作者：
本篇文章是對(duì)求子數(shù)組最大和的解決方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下
題目：輸入一個(gè)整形數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。數(shù)組中連續(xù)的一個(gè)或多個(gè)整數(shù)組成一個(gè)子數(shù)組，每個(gè)子數(shù)組都有一個(gè)和。求所有子數(shù)組的和的最大值。要求時(shí)間復(fù)雜度為O(n)。
例如輸入的數(shù)組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數(shù)組為3, 10, -4, 7, 2，因此輸出為該子數(shù)組的和18。
如果不考慮時(shí)間復(fù)雜度，我們可以枚舉出所有子數(shù)組并求出他們的和。不過非常遺憾的是，由于長(zhǎng)度為n的數(shù)組有O(n2)個(gè)子數(shù)組；而且求一個(gè)長(zhǎng)度為n的數(shù)組的和的時(shí)間復(fù)雜度為O(n)。因此這種思路的時(shí)間是O(n3)。
很容易理解，當(dāng)我們加上一個(gè)正數(shù)時(shí)，和會(huì)增加；當(dāng)我們加上一個(gè)負(fù)數(shù)時(shí)，和會(huì)減少。如果當(dāng)前得到的和是個(gè)負(fù)數(shù)，那么這個(gè)和在接下來的累加中應(yīng)該拋棄并重新清零，不然的話這個(gè)負(fù)數(shù)將會(huì)減少接下來的和。基于這樣的思路，我們可以寫出如下代碼：
/*
// Find the greatest sum of all sub-arrays
// Return value: if the input is valid, return true, otherwise return false
int *pData, // an array
unsigned int nLength, // the length of array
int &nGreatestSum // the greatest sum of all sub-arrays
*/
int start,end;
bool FindGreatestSumOfSubArray(int *pData, unsigned int nLength, int &nGreatestSum)
{
// if the input is invalid, return false
if((pData == NULL) || (nLength == 0))
return false;
int k=0;
int nCurSum = nGreatestSum = 0;
for(unsigned int i = 0; i < nLength; ++i)
{
nCurSum += pData[i];
// if the current sum is negative, discard it
if(nCurSum < 0)
{
nCurSum = 0;
k = i+1;
}
// if a greater sum is found, update the greatest sum
if(nCurSum > nGreatestSum)
{
nGreatestSum = nCurSum;
start = k;
end = i;
}
}
// if all data are negative, find the greatest element in the array
if(nGreatestSum == 0)
{
nGreatestSum = pData[0];
for(unsigned int i = 1; i < nLength; ++i)
{
if(pData[i] > nGreatestSum)
{
nGreatestSum = pData[i];
start = end = i;
}
}
}
return true;
}
討論：上述代碼中有兩點(diǎn)值得和大家討論一下：
• 函數(shù)的返回值不是子數(shù)組和的最大值，而是一個(gè)判斷輸入是否有效的標(biāo)志。如果函數(shù)返回值的是子數(shù)組和的最大值，那么當(dāng)輸入一個(gè)空指針是應(yīng)該返回什么呢？返回0？那這個(gè)函數(shù)的用戶怎么區(qū)分輸入無效和子數(shù)組和的最大值剛好是0這兩中情況呢？基于這個(gè)考慮，本人認(rèn)為把子數(shù)組和的最大值以引用的方式放到參數(shù)列表中，同時(shí)讓函數(shù)返回一個(gè)函數(shù)是否正常執(zhí)行的標(biāo)志。
• 輸入有一類特殊情況需要特殊處理。當(dāng)輸入數(shù)組中所有整數(shù)都是負(fù)數(shù)時(shí)，子數(shù)組和的最大值就是數(shù)組中的最大元素。
方法二：編程之美2.14
/**
求最大子數(shù)組和（編程之美2.14，返回下標(biāo)及首尾不相連）
** author :liuzhiwei
** date :2011-08-17
起始點(diǎn)與結(jié)束點(diǎn)下標(biāo)如何來記錄：
由于我要求起始點(diǎn)下標(biāo)、結(jié)束點(diǎn)下標(biāo)都靠前的子數(shù)組，所以我們?cè)趧?dòng)態(tài)規(guī)劃的時(shí)候最好從后向前遞推，這樣dp[i]表示的值就是以下標(biāo)i為開始的最大子數(shù)組的值，那么當(dāng)dp[i]與dp[j]相同時(shí)我們選取i,j中較小的下標(biāo)作為起點(diǎn)
**/
int maxSum(int *arr, int n, int & start, int & end)
{
int i , temp , dp , max ;
dp = max = arr[n-1];
start = end = n-1;
temp = n-1;
for(i = n - 2 ; i >= 0 ; --i)
{
if(dp > 0)
dp += arr[i];
else
{
dp = arr[i]; //拋棄當(dāng)前子序列
temp = i; //開始新的子序列搜索
}
if(dp > max) //更新最大子序列
{
max = dp;
end = temp;
start = i; //最大和增加，此時(shí)的i一定是最右端
}
}
return max;
}
//特殊測(cè)試用例 -10 -1 -4
另外一種從前往后遍歷的方法如下：
// 需要保存起始點(diǎn)與結(jié)束點(diǎn)下標(biāo)的時(shí)候，從前往后遍歷也是可以的
int MaxSum(int *a , int n)
{
int tempstart = 0 , sum=0 , max = -1000;
int i , start , end;
start = end = 0;
for(i = 0 ; i < n ; ++i)
{
if(sum < 0)
{
sum = a[i];
tempstart = i;
}
else
sum += a[i];
if(sum > max)
{
max = sum;
start = tempstart;
end = i;
}
}
return max;
}
拓展問題1：
如果認(rèn)為數(shù)組是環(huán)形的，即首尾相接(下標(biāo)n-1的元素后面的元素下標(biāo)為0)，求最大子段和。
解析：
我覺得這個(gè)問題要比第一個(gè)問題容易，有很多種方法解決。我介紹三種方法，但是其中一種我覺得有問題，但卻作為《編程之美》這本書的一道練習(xí)答案，也可能是我理解錯(cuò)作者的算法了，一會(huì)慢慢討論。
方法一：
這個(gè)問題的最優(yōu)解一定是以下兩種可能?？赡芤唬鹤顑?yōu)解沒有跨過a[n-1]到a[0]，即原問題，非環(huán)形數(shù)組?？赡芏鹤顑?yōu)解跨過a[n-1]到a[0]，新問題。
對(duì)于第一種情況，我們可以按照簡(jiǎn)單的動(dòng)態(tài)規(guī)劃解法求得，設(shè)為max1；對(duì)于第二種情況，可以將原問題轉(zhuǎn)化為數(shù)組的最小子段和問題，再用數(shù)組全部元素的和減去最小子段和，那么結(jié)果一定是跨過a[n-1]到a[0]情況中最大的子段和，設(shè)為max2。最終結(jié)果即為max1與max2中較大的那個(gè)。
例1：有數(shù)組6、-1、-6、8、2
求得max1=10，max2=16，則取較大的max2作為結(jié)果。
例2：有數(shù)組-6、8、2、6、-1
求得max1=16，max2=15，則取較大的max1作為結(jié)果。
可能有些同學(xué)會(huì)對(duì)為什么：數(shù)組元素“sum - 最小子段和 = 跨過a[n-1]到a[0]情況中的最大子段和”這一點(diǎn)有些疑問。我們可以這樣理解：n個(gè)數(shù)的和是一定的，那么如果我們?cè)谶@n個(gè)數(shù)中找到連續(xù)的一段數(shù)，并且這段數(shù)是所有連續(xù)的數(shù)的和最小的，那么“sum-最小子段和”的結(jié)果一定最大。故求得：跨過a[n-1]到a[0]情況中的最大子段和。
完整代碼如下：
//環(huán)形數(shù)組求最大子數(shù)組的和
int MaxSum(int *a , int n)
{
int i , sum , max1 , max2 , dp, min;
dp = max1 = a[0];
for(i = 1 ; i < n ; ++i) //最優(yōu)解沒有跨過a[n-1]到a[0]，即原問題，非環(huán)形數(shù)組
{
if(dp < 0)
dp = a[i];
else
dp += a[i];
if(dp > max1)
max1 = dp;
}
sum = min = dp = a[0];
for(i = 1 ; i < n ; ++i) //可以將原問題轉(zhuǎn)化為數(shù)組的最小子段和問題，再用數(shù)組全部元素的和減去最小子段和，那么結(jié)果一定是跨過a[n-1]到a[0]情況中最大的子段和
{
if(dp > 0)
dp = a[i];
else
dp += a[i];
if(dp < min)
min = dp;
sum += a[i];
}
max2 = sum - min; //數(shù)組全部元素的和減去最小子段和
return max1 > max2 ? max1 : max2;; //返回一個(gè)較大值
}
第一部分即求第一種情況的最大值max1（用變量Max代替），第二部分中最初tmp為最小子段和，然后tmp值為sum-tmp；最后Max取兩者較大的數(shù)。
方法二：
方法二將問題轉(zhuǎn)化成另外一個(gè)問題：既然一段數(shù)的首尾可以相接，那么我們可以將數(shù)組復(fù)制，并接到自己的后面，然后我們求新數(shù)組的最大子數(shù)組的和，但這里要限制一個(gè)條件，就是最大子數(shù)組的長(zhǎng)度不可以超過n。這樣我們就把問題轉(zhuǎn)化為拓展問題3了，我會(huì)在第三部分中介紹。
方法三：
方法三是《編程之美》這本書中介紹的，詳細(xì)見188頁，但是我覺得這種算法是錯(cuò)誤的，可能是我理解作者的思路有問題，我將解法抄在下面，并舉出一個(gè)反例，有興趣討論的同學(xué)希望能給我留言。
摘自《編程之美》P188：
如果數(shù)組(A[0],A[1],A[2],......,A[n-1])首尾相鄰，也就是我們?cè)试S找到一段數(shù)字(A[i],A[i+1],......A[n-1],A[0],A[1],....,A[j])，使其和最大，怎么辦？
(1)解沒有跨過A[n-1] 到A[0] (原問題)。
(2)解跨過A[n-1]到A[0]。
對(duì)于第2種情況，只要找到從A[0]開始和最大的一段（A[0],…,A[j]）（0<=j<n），以及以A[n-1]結(jié)尾的和最大的一段（A[i],…,A[n-1]）（0<=i<n），那么，第2種情況中，和的最大值M_2為：
M_2=A[i]+…+A[n-1]+A[0]+…+A[j]
如果i <= j，則
M_2=A[0]+…+A[n-1]
否則
M_2=A[0]+…+A[j]+A[i]+…+A[n-1]
最后，再取兩種情況的最大值就可以了，求解跨過A[n-1]到A[0]的情況只需要遍歷數(shù)組一次，故總時(shí)間復(fù)雜度為O(N)+O(N)=O(N)。
解析：
分為兩種情況討論是沒有問題的，但是對(duì)于第2種情況的解法我認(rèn)為是錯(cuò)誤的，反例：
求5個(gè)元素的數(shù)組6,-1,-6,8,2的最大子數(shù)組和：M_1為10，但是如果利用上面的方法，M_2求得的結(jié)果為9，因?yàn)閺腁[0]開始和最大的一段即為A[0],…,A[n-1]為9，以A[n-1]結(jié)尾的和最大的一段（A[i],…,A[n-1]）為A[n-1]，由于這兩段有相交，故M_2= A[0]+…+A[n-1]。
最終結(jié)果為9，取兩種情況較大的，那么結(jié)果為10。但是正確結(jié)果明顯為16。
出現(xiàn)這種結(jié)果的原因：從A[0]開始和最大的一段雖然求的沒有錯(cuò)，但是我們希望求得的結(jié)果并非是這一段，我們希望求得A[0]這一段，這樣就不會(huì)出現(xiàn)兩段相交的情況。
在第二部分中，我分析了兩個(gè)拓展問題，后面兩個(gè)拓展問題我會(huì)在第三部分中分析。
如果我上面有寫的不對(duì)的地方或者你有更好的方法，希望能提出來，互相學(xué)習(xí)嘛。
拓展問題2：
有一個(gè)整數(shù)數(shù)列，其中有負(fù)數(shù)、正數(shù)， 其中連續(xù)的幾個(gè)數(shù)求和，求和的絕對(duì)值最大的數(shù)字串。
分析
思路
最大子矩陣和
#include <iostream>
#include <cstdio>
using namespace std;
#include <memory.h>
int a[102][102];
int maxSubArray(int *arr, int len) //最大子序列和
{
int i,sum=arr[0],b=0;
for(i=0;i<len;++i)
{
if(b>0)
b+=arr[i];
else
b=arr[i];
if(b>sum)
sum=b;
}
return sum;
}
int maxSubMatrix(int n, int m,int array[102][102])
{
int i,j,h,max,sum=-100000;
int b[102];
for(i=0;i<n;i++)
{
memset(b,0,sizeof(b)); //初始化b[]
for(j=i;j<n;j++) //把第i行到第j行相加,對(duì)每一次相加求出最大值
{
for(h=0;h<m;h++)
{
b[h]+=array[j][h]; //二維數(shù)組壓縮成一維數(shù)組，然后求最大子序列和
}
max=maxSubArray(b,h);
if(max>sum)
sum=max;
}
}
return sum;
}
int main(void)
{
int n,i,j;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
}
printf("%d\n",maxSubMatrix(n,n,a));
}
return 0;
}
例如輸入的數(shù)組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數(shù)組為3, 10, -4, 7, 2，因此輸出為該子數(shù)組的和18。
如果不考慮時(shí)間復(fù)雜度，我們可以枚舉出所有子數(shù)組并求出他們的和。不過非常遺憾的是，由于長(zhǎng)度為n的數(shù)組有O(n2)個(gè)子數(shù)組；而且求一個(gè)長(zhǎng)度為n的數(shù)組的和的時(shí)間復(fù)雜度為O(n)。因此這種思路的時(shí)間是O(n3)。
很容易理解，當(dāng)我們加上一個(gè)正數(shù)時(shí)，和會(huì)增加；當(dāng)我們加上一個(gè)負(fù)數(shù)時(shí)，和會(huì)減少。如果當(dāng)前得到的和是個(gè)負(fù)數(shù)，那么這個(gè)和在接下來的累加中應(yīng)該拋棄并重新清零，不然的話這個(gè)負(fù)數(shù)將會(huì)減少接下來的和。基于這樣的思路，我們可以寫出如下代碼：
復(fù)制代碼 代碼如下:
/*
// Find the greatest sum of all sub-arrays
// Return value: if the input is valid, return true, otherwise return false
int *pData, // an array
unsigned int nLength, // the length of array
int &nGreatestSum // the greatest sum of all sub-arrays
*/
int start,end;
bool FindGreatestSumOfSubArray(int *pData, unsigned int nLength, int &nGreatestSum)
{
// if the input is invalid, return false
if((pData == NULL) || (nLength == 0))
return false;
int k=0;
int nCurSum = nGreatestSum = 0;
for(unsigned int i = 0; i < nLength; ++i)
{
nCurSum += pData[i];
// if the current sum is negative, discard it
if(nCurSum < 0)
{
nCurSum = 0;
k = i+1;
}
// if a greater sum is found, update the greatest sum
if(nCurSum > nGreatestSum)
{
nGreatestSum = nCurSum;
start = k;
end = i;
}
}
// if all data are negative, find the greatest element in the array
if(nGreatestSum == 0)
{
nGreatestSum = pData[0];
for(unsigned int i = 1; i < nLength; ++i)
{
if(pData[i] > nGreatestSum)
{
nGreatestSum = pData[i];
start = end = i;
}
}
}
return true;
}
討論：上述代碼中有兩點(diǎn)值得和大家討論一下：
• 函數(shù)的返回值不是子數(shù)組和的最大值，而是一個(gè)判斷輸入是否有效的標(biāo)志。如果函數(shù)返回值的是子數(shù)組和的最大值，那么當(dāng)輸入一個(gè)空指針是應(yīng)該返回什么呢？返回0？那這個(gè)函數(shù)的用戶怎么區(qū)分輸入無效和子數(shù)組和的最大值剛好是0這兩中情況呢？基于這個(gè)考慮，本人認(rèn)為把子數(shù)組和的最大值以引用的方式放到參數(shù)列表中，同時(shí)讓函數(shù)返回一個(gè)函數(shù)是否正常執(zhí)行的標(biāo)志。
• 輸入有一類特殊情況需要特殊處理。當(dāng)輸入數(shù)組中所有整數(shù)都是負(fù)數(shù)時(shí)，子數(shù)組和的最大值就是數(shù)組中的最大元素。
方法二：編程之美2.14
復(fù)制代碼 代碼如下:
/**
求最大子數(shù)組和（編程之美2.14，返回下標(biāo)及首尾不相連）
** author :liuzhiwei
** date :2011-08-17
起始點(diǎn)與結(jié)束點(diǎn)下標(biāo)如何來記錄：
由于我要求起始點(diǎn)下標(biāo)、結(jié)束點(diǎn)下標(biāo)都靠前的子數(shù)組，所以我們?cè)趧?dòng)態(tài)規(guī)劃的時(shí)候最好從后向前遞推，這樣dp[i]表示的值就是以下標(biāo)i為開始的最大子數(shù)組的值，那么當(dāng)dp[i]與dp[j]相同時(shí)我們選取i,j中較小的下標(biāo)作為起點(diǎn)
**/
int maxSum(int *arr, int n, int & start, int & end)
{
int i , temp , dp , max ;
dp = max = arr[n-1];
start = end = n-1;
temp = n-1;
for(i = n - 2 ; i >= 0 ; --i)
{
if(dp > 0)
dp += arr[i];
else
{
dp = arr[i]; //拋棄當(dāng)前子序列
temp = i; //開始新的子序列搜索
}
if(dp > max) //更新最大子序列
{
max = dp;
end = temp;
start = i; //最大和增加，此時(shí)的i一定是最右端
}
}
return max;
}
//特殊測(cè)試用例 -10 -1 -4
另外一種從前往后遍歷的方法如下：
復(fù)制代碼 代碼如下:
// 需要保存起始點(diǎn)與結(jié)束點(diǎn)下標(biāo)的時(shí)候，從前往后遍歷也是可以的
int MaxSum(int *a , int n)
{
int tempstart = 0 , sum=0 , max = -1000;
int i , start , end;
start = end = 0;
for(i = 0 ; i < n ; ++i)
{
if(sum < 0)
{
sum = a[i];
tempstart = i;
}
else
sum += a[i];
if(sum > max)
{
max = sum;
start = tempstart;
end = i;
}
}
return max;
}
拓展問題1：
如果認(rèn)為數(shù)組是環(huán)形的，即首尾相接(下標(biāo)n-1的元素后面的元素下標(biāo)為0)，求最大子段和。
解析：
我覺得這個(gè)問題要比第一個(gè)問題容易，有很多種方法解決。我介紹三種方法，但是其中一種我覺得有問題，但卻作為《編程之美》這本書的一道練習(xí)答案，也可能是我理解錯(cuò)作者的算法了，一會(huì)慢慢討論。
方法一：
這個(gè)問題的最優(yōu)解一定是以下兩種可能?？赡芤唬鹤顑?yōu)解沒有跨過a[n-1]到a[0]，即原問題，非環(huán)形數(shù)組?？赡芏鹤顑?yōu)解跨過a[n-1]到a[0]，新問題。
對(duì)于第一種情況，我們可以按照簡(jiǎn)單的動(dòng)態(tài)規(guī)劃解法求得，設(shè)為max1；對(duì)于第二種情況，可以將原問題轉(zhuǎn)化為數(shù)組的最小子段和問題，再用數(shù)組全部元素的和減去最小子段和，那么結(jié)果一定是跨過a[n-1]到a[0]情況中最大的子段和，設(shè)為max2。最終結(jié)果即為max1與max2中較大的那個(gè)。
例1：有數(shù)組6、-1、-6、8、2
求得max1=10，max2=16，則取較大的max2作為結(jié)果。
例2：有數(shù)組-6、8、2、6、-1
求得max1=16，max2=15，則取較大的max1作為結(jié)果。
可能有些同學(xué)會(huì)對(duì)為什么：數(shù)組元素“sum - 最小子段和 = 跨過a[n-1]到a[0]情況中的最大子段和”這一點(diǎn)有些疑問。我們可以這樣理解：n個(gè)數(shù)的和是一定的，那么如果我們?cè)谶@n個(gè)數(shù)中找到連續(xù)的一段數(shù)，并且這段數(shù)是所有連續(xù)的數(shù)的和最小的，那么“sum-最小子段和”的結(jié)果一定最大。故求得：跨過a[n-1]到a[0]情況中的最大子段和。
完整代碼如下：
復(fù)制代碼 代碼如下:
//環(huán)形數(shù)組求最大子數(shù)組的和
int MaxSum(int *a , int n)
{
int i , sum , max1 , max2 , dp, min;
dp = max1 = a[0];
for(i = 1 ; i < n ; ++i) //最優(yōu)解沒有跨過a[n-1]到a[0]，即原問題，非環(huán)形數(shù)組
{
if(dp < 0)
dp = a[i];
else
dp += a[i];
if(dp > max1)
max1 = dp;
}
sum = min = dp = a[0];
for(i = 1 ; i < n ; ++i) //可以將原問題轉(zhuǎn)化為數(shù)組的最小子段和問題，再用數(shù)組全部元素的和減去最小子段和，那么結(jié)果一定是跨過a[n-1]到a[0]情況中最大的子段和
{
if(dp > 0)
dp = a[i];
else
dp += a[i];
if(dp < min)
min = dp;
sum += a[i];
}
max2 = sum - min; //數(shù)組全部元素的和減去最小子段和
return max1 > max2 ? max1 : max2;; //返回一個(gè)較大值
}
第一部分即求第一種情況的最大值max1（用變量Max代替），第二部分中最初tmp為最小子段和，然后tmp值為sum-tmp；最后Max取兩者較大的數(shù)。
方法二：
方法二將問題轉(zhuǎn)化成另外一個(gè)問題：既然一段數(shù)的首尾可以相接，那么我們可以將數(shù)組復(fù)制，并接到自己的后面，然后我們求新數(shù)組的最大子數(shù)組的和，但這里要限制一個(gè)條件，就是最大子數(shù)組的長(zhǎng)度不可以超過n。這樣我們就把問題轉(zhuǎn)化為拓展問題3了，我會(huì)在第三部分中介紹。
方法三：
方法三是《編程之美》這本書中介紹的，詳細(xì)見188頁，但是我覺得這種算法是錯(cuò)誤的，可能是我理解作者的思路有問題，我將解法抄在下面，并舉出一個(gè)反例，有興趣討論的同學(xué)希望能給我留言。
摘自《編程之美》P188：
如果數(shù)組(A[0],A[1],A[2],......,A[n-1])首尾相鄰，也就是我們?cè)试S找到一段數(shù)字(A[i],A[i+1],......A[n-1],A[0],A[1],....,A[j])，使其和最大，怎么辦？
(1)解沒有跨過A[n-1] 到A[0] (原問題)。
(2)解跨過A[n-1]到A[0]。
對(duì)于第2種情況，只要找到從A[0]開始和最大的一段（A[0],…,A[j]）（0<=j<n），以及以A[n-1]結(jié)尾的和最大的一段（A[i],…,A[n-1]）（0<=i<n），那么，第2種情況中，和的最大值M_2為：
M_2=A[i]+…+A[n-1]+A[0]+…+A[j]
如果i <= j，則
M_2=A[0]+…+A[n-1]
否則
M_2=A[0]+…+A[j]+A[i]+…+A[n-1]
最后，再取兩種情況的最大值就可以了，求解跨過A[n-1]到A[0]的情況只需要遍歷數(shù)組一次，故總時(shí)間復(fù)雜度為O(N)+O(N)=O(N)。
解析：
分為兩種情況討論是沒有問題的，但是對(duì)于第2種情況的解法我認(rèn)為是錯(cuò)誤的，反例：
求5個(gè)元素的數(shù)組6,-1,-6,8,2的最大子數(shù)組和：M_1為10，但是如果利用上面的方法，M_2求得的結(jié)果為9，因?yàn)閺腁[0]開始和最大的一段即為A[0],…,A[n-1]為9，以A[n-1]結(jié)尾的和最大的一段（A[i],…,A[n-1]）為A[n-1]，由于這兩段有相交，故M_2= A[0]+…+A[n-1]。
最終結(jié)果為9，取兩種情況較大的，那么結(jié)果為10。但是正確結(jié)果明顯為16。
出現(xiàn)這種結(jié)果的原因：從A[0]開始和最大的一段雖然求的沒有錯(cuò)，但是我們希望求得的結(jié)果并非是這一段，我們希望求得A[0]這一段，這樣就不會(huì)出現(xiàn)兩段相交的情況。
在第二部分中，我分析了兩個(gè)拓展問題，后面兩個(gè)拓展問題我會(huì)在第三部分中分析。
如果我上面有寫的不對(duì)的地方或者你有更好的方法，希望能提出來，互相學(xué)習(xí)嘛。
拓展問題2：
有一個(gè)整數(shù)數(shù)列，其中有負(fù)數(shù)、正數(shù)， 其中連續(xù)的幾個(gè)數(shù)求和，求和的絕對(duì)值最大的數(shù)字串。
分析
思路
最大子矩陣和
復(fù)制代碼 代碼如下:
#include <iostream>
#include <cstdio>
using namespace std;
#include <memory.h>
int a[102][102];
int maxSubArray(int *arr, int len) //最大子序列和
{
int i,sum=arr[0],b=0;
for(i=0;i<len;++i)
{
if(b>0)
b+=arr[i];
else
b=arr[i];
if(b>sum)
sum=b;
}
return sum;
}
int maxSubMatrix(int n, int m,int array[102][102])
{
int i,j,h,max,sum=-100000;
int b[102];
for(i=0;i<n;i++)
{
memset(b,0,sizeof(b)); //初始化b[]
for(j=i;j<n;j++) //把第i行到第j行相加,對(duì)每一次相加求出最大值
{
for(h=0;h<m;h++)
{
b[h]+=array[j][h]; //二維數(shù)組壓縮成一維數(shù)組，然后求最大子序列和
}
max=maxSubArray(b,h);
if(max>sum)
sum=max;
}
}
return sum;
}
int main(void)
{
int n,i,j;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
}
printf("%d\n",maxSubMatrix(n,n,a));
}
return 0;
}
相關(guān)文章
C++成員函數(shù)如何當(dāng)作回調(diào)函數(shù)同時(shí)傳遞this指針
這篇文章主要介紹了C++成員函數(shù)如何當(dāng)作回調(diào)函數(shù)同時(shí)傳遞this指針，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-11-11
C語言完美實(shí)現(xiàn)動(dòng)態(tài)數(shù)組代碼分享
本文給大家分享的是一則使用C語言實(shí)現(xiàn)動(dòng)態(tài)數(shù)組的代碼，完美解決內(nèi)存溢出以及內(nèi)存回收問題，有需要的小伙伴可以參考下。2016-02-02
轉(zhuǎn)義字符是很多程序語言、數(shù)據(jù)格式和通信協(xié)議的形式文法的一部分。對(duì)于一個(gè)給定的字母表，一個(gè)轉(zhuǎn)義字符的目的是開始一個(gè)字符序列，使得轉(zhuǎn)義字符開頭的該字符序列具有不同于該字符序列單獨(dú)出現(xiàn)（沒有轉(zhuǎn)義字符開頭）時(shí)的語義。因此轉(zhuǎn)義字符開頭的字符序列被叫做轉(zhuǎn)義序列2022-04-04
putchar函數(shù)函數(shù)幾乎是在整個(gè)C語言中最沒有知名度的，它常常被程序員冷漠地對(duì)待，這篇文章主要介紹了C語言中的putchar函數(shù),需要的朋友可以參考下2022-12-12
深入HRESULT與Windows Error Codes的區(qū)別詳解
本篇文章是對(duì)HRESULT與Windows Error Codes的區(qū)別進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
有關(guān)C++中隨機(jī)函數(shù)rand() 和srand() 的用法詳解
下面小編就為大家?guī)硪黄嘘P(guān)C++中隨機(jī)函數(shù)rand() 和srand() 的用法詳解。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-01-01
大家好，本篇文章主要講的是C語言函數(shù)指針詳解，感興趣的同學(xué)趕快來看一看吧，對(duì)你有幫助的話記得收藏一下，方便下次瀏覽2022-01-01
迭代器是一種抽象的設(shè)計(jì)概念，它提供了一種方法，使之能夠依序巡訪某個(gè)聚合物（容器）所含的各個(gè)元素，而又無需暴露該聚合物的內(nèi)部表述方式。本文主要介了STL迭代器萃取的方法，需要的可以參考一下2022-11-11
Qt與Web混合開發(fā)實(shí)現(xiàn)雙向通信的示例
本文主要介紹了Qt與Web混合開發(fā)實(shí)現(xiàn)雙向通信的示例，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-07-07
C語言sizeof與字符串處理與動(dòng)態(tài)內(nèi)存分配及main函數(shù)參數(shù)詳解
這篇文章主要介紹了C語言字符串處理函數(shù)、sizeof、動(dòng)態(tài)內(nèi)存分配函數(shù)、main函數(shù)參數(shù)問題，static在修飾變量的時(shí)候，如果是修飾全局變量，則跟全局變量功能一樣，通過示例代碼給大家介紹的非常詳細(xì)，需要的朋友可以參考下2022-07-07