您的位置: 首页  >  IT文章  >  最大延续子序列和多解——HDU 1003

最大延续子序列和多解——HDU 1003

分类: IT文章 • 2024-06-10 23:27:06
最大连续子序列和多解——HDU 1003

对应HDU题目：点击打开链接

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 <stdio.h>
#include <stdlib.h>
#include <string.h>
#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<n; i++)
			scanf("%d", &a[i]);
		int max_s = -(1<<30);
		int sum, left, right;
		for(i=0; i<n; i++){
			for(j=i; j<n; j++){
				sum = 0;
				for(k=i; k<=j; k++)
					sum += a[k];
				if(sum > max_s){
					max_s = sum;
					left = i;
					right = j;
				}
			}
		}
		printf("Case %d:\n%d %d %d\n", ++w, max_s, left + 1, right + 1);
		if(T) printf("\n");
	}
	return 0;
}

方法二：对前i项和进行预处理，O（n^2），超时。 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#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:\n%d %d %d\n", ++w, max_s, left, right);
		if(T) printf("\n");
	}
	return 0;
}

方法三：分治，O（nlg(n)），可AC。 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#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; i++){
		v += A[i];
		if(v > 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<n; i++){
			scanf("%d", &a[i]);
		}
		max_s = Max_Ans(a, 0, n);
		printf("Case %d:\n%d %d %d\n", ++w, max_s.val, max_s.l + 1, max_s.r + 1);
		if(T) printf("\n");
	}
	return 0;
}

方法四：线段树，可AC。 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#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:\n%d %d %d\n", ++w, max_s.msum, max_s.ml, max_s.mr);
        if(T) printf("\n");
    }
    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.****.net/hcbbt/article/details/10454947

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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:\n%d %d %d\n", ++w, max_s, beg, end);
		if(T) printf("\n");
	}
	return 0;
}









相关推荐