例13 最大子段和 題目描述 給出一段序列，選出其中連續且非空的一段使得這段和最大。例如在序列2,-4,3,-1,2,-4,3中，最大的子段和為4，該子段為3,-1,2。 輸入格式 第一行是一個正整數N，表示了序列的長度。 第二行包含N個絕對值不大於10000的整數Ai ，描述了這段序列。 輸出格式 ...
例13 最大子段和
題目描述
給出一段序列，選出其中連續且非空的一段使得這段和最大。例如在序列2,-4,3,-1,2,-4,3中，最大的子段和為4，該子段為3,-1,2。
輸入格式
第一行是一個正整數N，表示了序列的長度。
第二行包含N個絕對值不大於10000的整數Ai ，描述了這段序列。
輸出格式
一個整數，為最大的子段和是多少。子段的最小長度為1。
輸入樣例
7
2 -4 3 -1 2 -4 3
輸出樣例
4
（1）編程思路。
可以從長度為n的數列的最左端（設為數組元素a[1]）開始掃描，一直到最右端（設為數組元素a[n-1]）為止，記下所遇到的最大總和的子序列。
程式中定義變數maxsum保存最大連續子段和，cursum保存當前連續子段和。
初始時，cursum=a[0]、maxsum=a[0]。用迴圈for (i=1;i<n;i++)對序列中的每一個元素a[i]進行掃描處理。
在這一掃描過程中，從左到右記錄當前子序列的和（即cursum= cursum+a[i]），若這個和不斷增加（即當前a[i]為正，從而使cursum+a[i]>maxsum成為可能），那麼最大子序列的和maxsum也增加，從而更新maxsum。如果往右掃描中遇到負數，那麼當前子序列的和cursum會減小，此時cursum將會小於maxsum，maxsum也就不更新；如果掃描到a[i]時，cursum降到0時，說明前面已經掃描的那一段就可以拋棄了，這時需要將cursum置為0。這樣，cursum將從i之後的子段進行分析，若有比當前maxsum大的子段，需要更新maxsum。這樣一趟掃描結束後，就可以得到正確結果。
（2）源程式。
#include <stdio.h>
int main()
{
int a[200001];
int n,i,maxsum,cursum;
scanf("%d",&n);
for (i=0;i<n;i++)
scanf("%d",&a[i]);
cursum=a[0];
maxsum=a[0];
for (i=1;i<n;i++)
{
if (cursum+a[i]>maxsum)
{
maxsum=cursum+a[i];
}
if (cursum+a[i]<0)
{
cursum=0;
}
else
cursum= cursum+a[i] ;
}
printf("%d\n",maxsum);
return 0;
}
習題13
13-1 最大差值
本題選自洛谷題庫 （https://www.luogu.org/problem/P5146）
題目描述
HKE最近熱衷於研究序列，有一次他發現了一個有趣的問題：
對於一個序列A1 ,A2 ⋯An ，找出兩個數i,j，1≤i<j≤n，使得Aj −Ai 最大。
現在給出這個序列，請找出Aj −Ai 的最大值。
輸入格式
第一行為一個正整數n。
接下來n個整數，第k+1個整數為Ak 。
輸出格式
一行為 (Aj −Ai )的最大值
輸入樣例
10
1 3 4 6 7 9 10 1 2 9
輸出樣例
9
（1）編程思路。
由於求Aj −Ai 的最大值的要求是下標j>i，也就是說最大的數是在最小的數後面才符合要求，因此不能簡單地求序列的一個最大數max和一個最小數min（無法保證max一定在min的後面），然後輸出max-min作為答案。
定義變數minnum保存序列的最小數，maxdiff保存最大差值，由於輸入n>=2，因此可以先輸入序列前兩個數a和b，賦minnum的初值為a與b中的較小數，maxdiff的初值為b-a。
然後用迴圈for (i=3;i<=n;i++)對序列中的每一個元素Ai進行掃描處理。處理時，若當前Ai與最小數minnum的差值大於maxdiff，則更新maxdiff，這個更新一定是有效的，因為保存的最小數minnum一定在當前數Ai之前；若當前數Ai比最小數小，則更新最小數minnum為當前數Ai。
這樣一趟掃描結束後，就可以得到正確結果。
（2）源程式。
#include <stdio.h>
int main()
{
int minnum,maxdiff;
int i,n,a,b;
scanf("%d",&n);
scanf("%d%d",&a,&b);
minnum=a<b?a:b;
maxdiff=b-a;
for (i=3;i<=n;i++)
{
scanf("%d",&a);
if (a<minnum) minnum=a;
if (a-minnum>maxdiff) maxdiff=a-minnum;
}
printf("%d\n",maxdiff);
return 0;
}
13-2 連續自然數和
題目描述
對一個給定的自然數M，求出所有的連續的自然數段，這些連續的自然數段中的全部數之和為M。
例子：1998+1999+2000+2001+2002 = 10000，所以從1998到2002的一個自然數段為M=10000的一個解。
輸入格式
包含一個整數的單獨一行給出M的值（10≤M≤2,000,000）。
輸出格式
每行兩個自然數，給出一個滿足條件的連續自然數段中的第一個數和最後一個數，兩數之間用一個空格隔開，所有輸出行的第一個按從小到大的升序排列，對於給定的輸入數據，保證至少有一個解。
輸入樣例
10000
輸出樣例
18 142
297 328
388 412
1998 2002
（1）編程思路。
定義兩個變數left和right用於指示待求子序列的最左端和最右端，初始時令left=1，right=(int)sqrt(2.0*n)，顯然此時1+2+…+right的和值sum（sum=(right-left+1)*(left+right)/2）會非常接近n。之後進行如下操作過程：
1）比較sum與n，根據sum與n的大小關係進行不同處理。簡單描述就是若sum值大了，去掉子序列最左端的數，從而減少sum值；若sum值小了，將最右端數的下一個數加入子序列，從而增大sum值；若sum與n相等，則找到一個子序列的和等於n，輸出此時子序列的left和right值，輸出後和值sum中去掉子序列最左端的數以便繼續向後找到其他的子序列。
2）重覆上面的過程，直到left==right，此時子序列中只有一個數，搜索結束，退出。
（2）源程式。
#include <stdio.h>
#include <math.h>
int main()
{
int left,right,sum,n;
scanf("%d",&n);
left=1; right=(int)sqrt(2.0*n);
sum=(right-left+1)*(left+right)/2;
while (left<right)
{
if (sum==n)
{
printf("%d %d\n",left,right);
sum-=left++;
}
else if (sum<n)
{
right++;
sum+=right;
}
else
{
sum-=left;
left++;
}
}
return 0;
}
13-3 Subsequence
本題選自北大POJ 題庫（http://poj.org/problem?id=3061）。
Description
A sequence of N positive integers (10 < N < 100 000), each of them less than or equal 10000, and a positive integer S (S < 100 000 000) are given. Write a program to find the minimal length of the subsequence of consecutive elements of the sequence, the sum of which is greater than or equal to S.
Input
The first line is the number of test cases. For each test case the program has to read the numbers N and S, separated by an interval, from the first line. The numbers of the sequence are given in the second line of the test case, separated by intervals. The input will finish with the end of file.
Output
For each the case the program has to print the result on separate line of the output file.if no answer, print 0.
Sample Input
2
10 15
5 1 3 5 10 7 4 9 2 8
5 11
1 2 3 4 5
Sample Output
2
3
（1）編程思路。
本題題意是：輸入整數N和S，N表示數列中元素的個數，S表示一個和值，然後輸入數列中的N個元素，求一個子序列長度最短的連續子序列，使子序列中全部元素的和大於等於S。輸出這個子序列的長度。
用兩個變數i和j表示子序列的兩個端點，初始時i和j的值均為0，和值sum=0。
這個搜索過程簡單描述為：先讓右端點移動，並將右端點的值累加到和值sum中（語句為sum+=a[j++]），直到sum大於等於S，按要求更新答案；然後再讓左端點移動，並將左端點的值從和值sum中減掉（語句為sum-=a[i++];），也隨之更新答案，直到出現sum小於S後，右端點再移動。重覆這個過程，直到右端點越過了原序列的最後一個數據。
（2）源程式。
#include <stdio.h>
int main()
{
int t,i,j,a[100001],n,s,sum,minx;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&s);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
i=0;
minx=0x7fffffff;
sum=0;
for (j=0;j<n;)
{
while(sum<s && j<n)
sum+=a[j++];
while(sum>=s)
{
if (minx>j-i) minx=j-i;
sum-=a[i++];
}
}
if (minx==0x7fffffff)
minx=0;
printf("%d\n",minx);
}
return 0;
}
