496
編程之美之2.14 求數組的子數組之和的最大值
【題目】
一個有N個整數元素的一維數組(A[0],A[1],A[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]返回8
【解法一】
設Sum[i,...,j]為數組A中第i個元素到第j個元素的和(0<=i<=j<n),遍曆所有的Sum[i,...,j]。
對每個整數對，我們都要計算x[i...j]的總和，並檢驗該總和是否大於迄今為止的最大總和。
/*********************************
* 日期：2014-5-19
* 作者：SJF0115
* 題目: 2.14 求數組的子數組之和的最大值
* 來源：編程之美
**********************************/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <limits.h>
using namespace std;
#define N 1001
int array[N];
int main(){
int n,i,j,k,sum;
//freopen("C:\\Users\\XIAOSI\\Desktop\\acm.txt","r",stdin);
while(scanf("%d",&n) != EOF){
//輸入數據
for(i = 0;i < n;i++){
scanf("%d",&array[i]);
}
int maxSum = INT_MIN;
// i 遍曆數組起點 j 遍曆數組終點
for(i = 0;i < n;i++){
for(j = i;j < n;j++){
sum = 0;
//遍曆所有可能的Sum[i..j]
for(k = i;k <= j;k++){
sum += array[k];
}
maxSum = max(maxSum,sum);
}
}
printf("%d\n",maxSum);
}
return 0;
}
時間複雜度為O（n^3）。程序運行速度很慢。
【解法二】
x[i...j]的總和與前麵已經計算出的x[i...j-1]的總和密切相關，Sum[i..j] = Sum[i...j-1]+array[j] 則可以將上麵算法中最後一個循環去掉，
避免重複計算，從而使算法得以改進。
時間複雜度為O（n^2）。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <limits.h>
using namespace std;
#define N 1001
int array[N];
int main(){
int n,i,j,k,sum;
//freopen("C:\\Users\\XIAOSI\\Desktop\\acm.txt","r",stdin);
while(scanf("%d",&n) != EOF){
//輸入數據
for(i = 0;i < n;i++){
scanf("%d",&array[i]);
}
int maxSum = INT_MIN;
// i 遍曆數組起點 j 遍曆數組終點
for(i = 0;i < n;i++){
sum = 0;
for(j = i;j < n;j++){
sum += array[j];
maxSum = max(maxSum,sum);
}
}
printf("%d\n",maxSum);
}
return 0;
}
【解法三】
通過訪問外循環執行之前就以構建好的數據結構的方式在內循環中計算總和。
即常見的前綴和技巧。令Sumi=A0+A1+A2+…+Ai，規定Sum0=A0，則可以在O(1)時間內求出子序列的值：Ai+Ai+1+…+Aj=Sumj-Sumi-1。這樣，時間複雜度降為O(n2)。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 1001
int array[N];
int sum[N];
int main(){
int n,i,j;
//freopen("C:\\Users\\XIAOSI\\Desktop\\acm.txt","r",stdin);
while(scanf("%d",&n) != EOF){
//輸入數據
for(i = 0;i < n;i++){
scanf("%d",&array[i]);
//計算前綴和
if(i != 0){
sum[i] = sum[i-1] + array[i];
}
else{
sum[i] = array[i];
}
}
int maxSum = sum[0];
// i 遍曆數組起點 j 遍曆數組終點
for(i = 0;i < n;i++){
for(j = i+1;j < n;j++){
maxSum = max(maxSum,sum[j] - sum[i]);
}
}
printf("%d\n",maxSum);
}
return 0;
}
【解法四】 分治策略
如果將所給數組(A[0],...,A[n-1])分為長度相等的兩段數組(A[0],...,A[n/2-1])和(A[n/2],...,A[n-1]),分別求出這兩段數組各自最大子段和，則原數組(A[0],...,A[n-1])的最大子段和分為以下三種情況，要麼在前半部分a中，要麼在後半部分b中，要麼跨越a和b之間的邊界：
a.(A[0],...,A[n-1])的最大子段和與(A[0],...,A[n/2-1])的最大子段和相同；
b.(A[0],...,A[n-1])的最大子段和與(A[n/2],...,A[n-1])的最大子段和相同；
c.(A[0],...,A[n-1])的最大子段跨過其中間兩個元素A[n/2-1]到A[n/2].
對應a和b兩個問題是規模減半的兩個相同的子問題，可以用遞歸求得。
對於c,需要找到以A[n/2-1]結尾的和最大的一段數組和S1=(A[i],...,A[n/2-1])和以A[n/2]開始和最大的一段和S2=(A[n/2],...,A[j]),那麼第三種情況的最大值為S1+S2。隻需要對原數組進行一次遍曆即可。在a中的部分是a中包含右邊界的最大子數組，在b中的部分是b中包含左邊界的最大子數組。
這其實是一種分治策略，時間複雜度為O（nlogn）。
/*********************************
* 日期：2014-5-20
* 作者：SJF0115
* 題目: 2.14 求數組的子數組之和的最大值
* 來源：編程之美
**********************************/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 1001
int array[N];
int MaxSubsequence(int L,int R){
int i,j;
//0個元素
if(L > R){
return 0;
}
//1個元素
if(L == R){
return array[L];
}
int mid = (L + R) / 2;
//跨越a和b之間的部分
//在a中的部分是a中包含右邊界的最大子數組
int sum = 0;
int leftMax = array[mid];
for(i = mid;i >= L;i--){
sum += array[i];
leftMax = max(leftMax,sum);
}
//在b中的部分是b中包含左邊界的最大子數組
sum = 0;
int rightMax = array[mid+1];
for(i = mid+1;i <= R;i++){
sum += array[i];
rightMax = max(rightMax,sum);
}
//遞歸調用
//跨越a和b
int maxSum = rightMax+leftMax;
//整個在a中
maxSum = max(maxSum,MaxSubsequence(L,mid));
//整個在b中
maxSum = max(maxSum,MaxSubsequence(mid+1,R));
return maxSum;
}
int main(){
int n,i,j;
//freopen("C:\\Users\\XIAOSI\\Desktop\\acm.txt","r",stdin);
while(scanf("%d",&n) != EOF){
//輸入數據
for(i = 0;i < n;i++){
scanf("%d",&array[i]);
}
int maxSum = MaxSubsequence(0,n-1);
printf("%d\n",maxSum);
}
return 0;
}
【解法五】
利用動態規劃做題。
隻遍曆數組一遍，當從頭到尾部遍曆數組A， 遇到一個數有兩種選擇 （1）加入之前subArray （2）自己另起一個subArray
設狀態S[i], 表示以A[i]結尾的最大連續子序列和，狀態轉移方程如下:
S[i] = max(S[i-1] + A[i],A[i])
時間複雜度：O(n) 空間複雜度：O(n)
【代碼五】
/*--------------------------------------------
* 日期：2015-02-03
* 作者：SJF0115
* 題目: 53.Maximum Subarray
* 網址：https://oj.leetcode.com/problems/maximum-subarray/
* 結果：AC
* 來源：LeetCode
* 博客：
-----------------------------------------------*/
class Solution {
public:
int maxSubArray(int A[], int n) {
int S[n];
int maxSum = A[0];
S[0] = A[0];
// 動態規劃
for(int i = 1;i < n;i++){
S[i] = max(S[i-1] + A[i],A[i]);
if(S[i] > maxSum){
maxSum = S[i];
}//if
}//for
return maxSum;
}
};
【解法六】
對前一個方法繼續優化，從狀態轉移方程上S【i】隻與S【i-1】有關，與其他都無關，因此可以用一個變量來記住前一個的最大連續數組和就可以了。
這樣就可以節省空間了。
時間複雜度：O(n) 空間複雜度：O(1)
【代碼六】
/*--------------------------------------------
* 日期：2015-02-03
* 作者：SJF0115
* 題目: 53.Maximum Subarray
* 網址：https://oj.leetcode.com/problems/maximum-subarray/
* 結果：AC
* 來源：LeetCode
* 博客：
-----------------------------------------------*/
class Solution {
public:
int maxSubArray(int A[], int n) {
int maxSum = A[0];
// sum 記住前一個的最大連續數組和
int sum = 0;
// 動態規劃
for(int i = 0;i < n;i++){
sum += A[i];
sum = max(sum,A[i]);
if(sum > maxSum){
maxSum = sum;
}//if
}//for
return maxSum;
}
};
【解法七】
/*********************************
* 日期：2015-01-27
* 作者：SJF0115
* 題目: 53.Maximum Subarray
* 網址：https://oj.leetcode.com/problems/maximum-subarray/
* 結果：AC
* 來源：LeetCode
* 博客：
**********************************/
#include <iostream>
#include <climits>
using namespace std;
class Solution {
public:
int maxSubArray(int A[], int n) {
if(n <= 0){
return 0;
}//if
// 最大和
int max = A[0];
// 當前最大和
int cur = 0;
for(int i = 0;i < n;++i){
// 一旦當前最大和小於0就重置為0,一個負數隻能使最大和變小
if(cur < 0){
cur = 0;
}//if
cur += A[i];
if(cur > max){
max = cur;
}//if
}//for
return max;
}
};
int main(){
Solution solution;
int n = 9;
int A[] = {-2,1,-3,4,-1,2,1,-5,4};
int result = solution.maxSubArray(A,n);
// 輸出
cout<<result<<endl;
return 0;
}
【相似題目】
最後更新：2017-04-03 08:26:14