最大連續子序列和多解——HDU 1003
Max Sum
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 161486 Accepted Submission(s): 37830
Problem Description Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.
Input The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).
Output For each test case, you should output two lines. The first line is Case #:, # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.
Sample Input
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
Sample Output
Case 1:
14 1 4
Case 2:
7 1 6
題意：T組數，每組一個數n，之後n個數。求n個數的最大連續子序列和與起始位置跟終點位置，如果有多個解，輸出起點最小的，如有多個終點，輸出終點最小的。
方法一：直接枚舉。O（n^3），超時
#include
#include
#include
#define N 100010
int a[N];
int main()
{
//freopen(in.txt, r, stdin);
int T, n, w = 0;
int i, j, k;
scanf(%d, &T);
while(T--)
{
scanf(%d, &n);
for(i=0; i max_s){
max_s = sum;
left = i;
right = j;
}
}
}
printf(Case %d:
%d %d %d
, ++w, max_s, left + 1, right + 1);
if(T) printf(
);
}
return 0;
}
方法二：對前i項和進行預處理，O（n^2），超時。
#include
#include
#include
#define N 100010
int a[N];
int sum[N];
int main()
{
//freopen(in.txt, r, stdin);
int T, n, w = 0;
int i, j, k;
scanf(%d, &T);
while(T--)
{
memset(sum, 0, sizeof(sum));
scanf(%d, &n);
for(i=1; i<=n; i++){
scanf(%d, &a[i]);
sum[i] = sum[i-1] + a[i];
}
int max_s = -(1<<30);
int s, left, right;
for(i=1; i<=n; i++){
for(j=i; j<=n; j++){
s = sum[j] - sum[i-1];
if(s > max_s){
max_s = s;
left = i;
right = j;
}
}
}
printf(Case %d:
%d %d %d
, ++w, max_s, left, right);
if(T) printf(
);
}
return 0;
}
方法三：分治，O（nlg(n)），可AC。
#include
#include
#include
#define N 100010
int a[N];
typedef struct NODE
{
int val, l, r;
}Node;
Node Max_Ans(int *A, int l, int r)
{
Node t;
if(1 == r - l){
t.val = A[l];
t.l = l;
t.r = l;
return t;
}
Node t1, t2, t3;
int mid = l + (r - l) / 2;
t1 = Max_Ans(A, l, mid);
t2 = Max_Ans(A, mid, r);
if(t1.val >= t2.val) t = t1;
else t = t2;
int i, v, L, R;
v = 0; L = A[mid -1]; t3.l = mid - 1;
for(i=mid-1; i>=l; i--){
v += A[i];
if(v >= L){
L = v;
t3.l = i;
}
}
v = 0; R = A[mid]; t3.r = mid;
for(i=mid; i R){
R = v;
t3.r = i;
}
}
t3.val = L + R;
if(t3.val >= t.val)
t = t3;
return t;
}
int main()
{
//freopen(in.txt, r, stdin);
int T, w = 0;
int n;
Node max_s;
int i, k;
scanf(%d, &T);
while(T--)
{
scanf(%d, &n);
for(i=0; i
方法四：線段樹，可AC。
#include
#include
#include
#define ms(x,y) memset(x,y,sizeof(x))
#define MAX(x,y) ((x)>(y)?(x):(y))
#define LL long long
const int MAXN=100000+10;
const int INF=1<<30;
using namespace std;
int sum[MAXN<<2];
int msum[MAXN<<2];
int lsum[MAXN<<2];
int rsum[MAXN<<2];
int ll[MAXN<<2];
int lr[MAXN<<2];
int ml[MAXN<<2];
int mr[MAXN<<2];
int rl[MAXN<<2];
int rr[MAXN<<2];
void up(int root)
{
int lroot = root<<1;
int rroot = root<<1|1;
sum[root] = sum[lroot] + sum[rroot];
lsum[root] = lsum[lroot];
rsum[root] = rsum[rroot];
//維護前綴
ll[root] = ll[lroot];
lr[root] = lr[lroot];
int sl = sum[lroot] + lsum[rroot];
if(sl > lsum[root]){
lsum[root] = sl;
lr[root] = lr[rroot];
}
//維護後綴
rl[root] = rl[rroot];
rr[root] = rr[rroot];
int sr = sum[rroot] + rsum[lroot];
if(sr >= rsum[root]){
rsum[root] = sr;
rl[root] = rl[lroot];
}
//維護區間最值
ml[root] = ml[lroot];
mr[root] = mr[lroot];
msum[root] = msum[lroot];
if(msum[root] < rsum[lroot] + lsum[rroot]){
msum[root] = rsum[lroot] + lsum[rroot];
ml[root] = rl[lroot];
mr[root] = lr[rroot];
}
if(msum[root] < msum[rroot]){
msum[root] = msum[rroot];
ml[root] = ml[rroot];
mr[root] = mr[rroot];
}
}
void Build(int root, int left, int right)
{
if(left == right){
scanf(%d, &sum[root]);
lsum[root] = sum[root]; ll[root] = left; lr[root] = right;
msum[root] = sum[root]; ml[root] = left; mr[root] = right;
rsum[root] = sum[root]; rl[root] = left; rr[root] = right;
return;
}
int mid = (left + right)>>1;
Build(root<<1, left, mid);
Build(root<<1|1, mid+1, right);
up(root);
}
struct Node
{
int msum, lsum, rsum, sum;
int ll, lr, ml, mr, rl, rr;
};
Node query(int root, int left, int right, int l, int r)
{
if(l == left && right == r){
Node N;
N.sum = sum[root];
N.msum = msum[root];
N.lsum = lsum[root];
N.rsum = rsum[root];
N.ll = ll[root];
N.lr = lr[root];
N.ml = ml[root];
N.mr = mr[root];
N.rl = rl[root];
N.rr = rr[root];
return N;
}
int mid = (left + right)>>1;
Node res,res1,res2;
int lroot = root<<1;
int rroot = root<<1|1;
int markl = 0, markr = 0;
if(r <= mid) return res = query(lroot, left, mid, l, r);
if(l > mid) return res2 = query(rroot, mid+1, right, l, r);
else{
res = query(lroot, left, mid, l, mid);
res2 = query(rroot, mid+1, right, mid+1, r);
res1.sum = res.sum + res2.sum;
res1.lsum = res.lsum;
res1.rsum = res2.rsum;
res1.ll = res.ll;
res1.lr = res.lr;
LL sl = res.sum + res2.lsum;
if(sl > res1.lsum){
res1.lsum = sl;
res1.lr = res2.lr;
}
res1.rl = res2.rl;
res1.rr = res2.rr;
LL sr = res2.sum + res.rsum;
if(sr >= res1.rsum){
res1.rsum = sr;
res1.rl = res.rl;
}
res1.msum = res.msum;
res1.ml = res.ml;
res1.mr = res.mr;
if(res1.msum < res.rsum + res2.lsum){
res1.msum = res.rsum + res2.lsum;
res1.ml = res.rl;
res1.mr = res2.lr;
}
if(res1.msum < res2.msum){
res1.msum = res2.msum;
res1.ml = res2.ml;
res1.mr = res2.mr;
}
return res1;
}
}
int main()
{
//freopen(in.txt, r, stdin);
int T, n, w = 0;
int i, j, k;
Node max_s;
scanf(%d, &T);
while(T--)
{
scanf(%d, &n);
Build(1, 1, n);
max_s = query(1, 1, n, 1, n);
printf(Case %d:
%d %d %d
, ++w, max_s.msum, max_s.ml, max_s.mr);
if(T) printf(
);
}
return 0;
}
方法五：掃一遍，累加sum， 當sum < 0 時，置sum 為0。如：
-1 5 7 -9 2 -7 -2 1 3 可分成
-1 | 5 12 3 5 | -7 | -2 | 1 4
豎線為分界。比較每個區間，取最大值。
思路來自：http://blog.csdn.net/hcbbt/article/details/10454947
#include
#include
#include
int main()
{
//freopen(in.txt, r, stdin);
int T, w = 0;
int n, num;
int beg, end, max_s, tmp;
int i, k;
scanf(%d, &T);
while(T--)
{
scanf(%d, &n);
max_s = -(1<<30);
tmp = 0;
beg = end = k = 1;
for(i=1; i<=n; i++){
scanf(%d, &num);
tmp += num;
if(tmp > max_s){
max_s = tmp;
beg = k;
end = i;
}
if(tmp < 0){
tmp = 0;
k = i + 1;
}
}
printf(Case %d:
%d %d %d
, ++w, max_s, beg, end);
if(T) printf(
);
}
return 0;
}
