程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 最大連續子序列和多解——HDU 1003

最大連續子序列和多解——HDU 1003

編輯:C++入門知識

最大連續子序列和多解——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;
}


 

 

 

 

 

 

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved