HDU 1231.最大连续子序列

234

题目


Description  


给定K个整数的序列{ N1, N2, ..., NK },其任意连续子序列可表示为{ Ni, Ni+1, ...,
Nj },其中 1 <= i <= j <= K。最大连续子序列是所有连续子序列中元素和最大的一个,
例如给定序列{ -2, 11, -4, 13, -5, -2 },其最大连续子序列为{ 11, -4, 13 },最大和
为20。
在今年的数据结构考卷中,要求编写程序得到最大和,现在增加一个要求,即还需要输出该
子序列的第一个和最后一个元素。


Input  


测试输入包含若干测试用例,每个测试用例占2行,第1行给出正整数K( < 10000 ),第2行给出K个整数,中间用空格分隔。当K为0时,输入结束,该用例不被处理。


Output  


对每个测试用例,在1行里输出最大和、最大连续子序列的第一个和最后一个元
素,中间用空格分隔。如果最大连续子序列不唯一,则输出序号i和j最小的那个(如输入样例的第2、3组)。若所有K个元素都是负数,则定义其最大和为0,输出整个序列的首尾元素。


Sample Input  


6
-2 11 -4 13 -5 -2
10
-10 1 2 3 4 -5 -23 3 7 -21
6
5 -8 3 2 5 0
1
10
3
-1 -5 -2
3
-1 0 -2
0


Sample Output  


20 11 13
10 1 4
10 3 5
10 10 10
0 -1 -2
0 0 0


题解



曾经做过**>类似的题目<**
两种思路:
  • 动态规划(这个专题要求的)
  • 递归与分治(类似的题目使用的方法)

先测试之前的代码,可以AC
换用动态规划

思路是:对于某一个值,可以选择将它加入到子序列里,或者选择从它开始一个新的子序列
也即dp[i] = max(dp[i-1]+a[i] , a[i])

然后查找dp中最大的值即可

~~其实我觉得处理起始和末尾才是最难的~~

末尾就是找到dp中最大值对应的下标指向的序列中的数字
起始需要从末尾开始往前倒推

代码


动态规划


/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい?
エリーチカ!
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
using namespace std;

const int INF = 0x7FFFFFFF;

const int maxn = 10005;
int dp[maxn];
int a[maxn];

bool Do() {
int n;
scanf("%d",&n);
if(n == 0)
return false;

memset(dp,0,sizeof(dp));

for(int i = 1;i <= n;i++) {
scanf("%d",&a[i]);
dp[i] = max(dp[i - 1] + a[i],a[i]);
}


int begin,end = a[1],Max = dp[1],pos=1;
for(int i = 1;i <= n;i++) {
if(dp[i] > Max) {
Max = dp[i];
end = a[i];
pos = i;
}
}
int sum = 0;
begin = a[pos];
for(int i = pos;i > 0;i--) {
if(Max > sum) {
sum += a[i];
begin = a[i];
} else {
break;
}
}
if(Max >= 0)
printf("%d %d %d\n",Max,begin,end);
else
printf("%d %d %d\n",0,a[1],a[n]);
return true;
}

int main() {

while(Do());
return 0;
}


递归与分治


/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい?
エリーチカ!
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
using namespace std;

const int maxn = 100005;
//const int INF = (1 << 31) - 1;
const int INF = 0x7fffffff;

int a[maxn];

int dfs(int *a,int l,int r,int &begin,int &end) {
if(l == r) {
begin = end = l;
return a[l];
}
if(l > r) {

begin = end = -1;
return -INF;
}



int mid = (l + r) / 2;
int Max;
int ans;
int tbegin,tend;
begin = end = mid;


//中间
int i;

ans = 0;
int maxl = 0;
for(i = mid - 1;i >= l;i--) {
ans += a[i];
if(ans >= maxl) {
maxl = ans;
begin = i;
}
}

ans = 0;
int maxr = 0;
for(i = mid + 1;i <= r;i++) {
ans += a[i];
if(ans > maxr) {
maxr = ans;
end = i;
}

}


Max = maxl + a[mid] + maxr;


//左侧
ans = dfs(a,l,mid - 1,tbegin,tend);
if(ans >= Max) {
Max = ans;
begin = tbegin;
end = tend;
}


//右侧
ans = dfs(a,mid + 1,r,tbegin,tend);
if(ans > Max) {
Max = ans;
begin = tbegin;
end = tend;
}

return Max;
}


bool Do() {
int n,l,r;
scanf("%d",&n);
if(n== 0)
return false;

for(int i = 1;i <= n;i++)
scanf("%d",&a[i]);

int ans = dfs(a,1,n,l,r);

if(ans >= 0)
printf("%d %d %d\n",ans,a[l],a[r]);
else
printf("%d %d %d\n",0,a[1],a[n]);

return true;
}

int main() {

while(Do());
return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论