[html] view plaincopyprint?題目描述：
給定K個整數的序列{ N1, N2, ..., NK }，其任意連續子序列可表示為{ Ni, Ni+1, ..., Nj }，其中 1 <= i <= j <= K。最大連續子序列是所有連續子序列中元素和最大的一個，例如給定序列{ -2, 11, -4, 13, -5, -2 }，其最大連續子序列為{ 11, -4, 13 }，最大和為20。現在增加一個要求，即還需要輸出該子序列的第一個和最後一個元素。
輸入：
測試輸入包含若干測試用例，每個測試用例占2行，第1行給出正整數K( K< 10000 )，第2行給出K個整數，中間用空格分隔。當K為0時，輸入結束，該用例不被處理。
輸出：
對每個測試用例，在1行裡輸出最大和、最大連續子序列的第一個和最後一個元素，中間用空格分隔。如果最大連續子序列不唯一，則輸出序號i和j最小的那個（如輸入樣例的第2、3組）。若所有K個元素都是負數，則定義其最大和為0，輸出整個序列的首尾元素。
樣例輸入：
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
樣例輸出：
20 11 13
10 1 4
10 3 5
10 10 10
0 -1 -2
0 0 0
題目描述：
給定K個整數的序列{ N1, N2, ..., NK }，其任意連續子序列可表示為{ Ni, Ni+1, ..., Nj }，其中 1 <= i <= j <= K。最大連續子序列是所有連續子序列中元素和最大的一個，例如給定序列{ -2, 11, -4, 13, -5, -2 }，其最大連續子序列為{ 11, -4, 13 }，最大和為20。現在增加一個要求，即還需要輸出該子序列的第一個和最後一個元素。
輸入：
測試輸入包含若干測試用例，每個測試用例占2行，第1行給出正整數K( K< 10000 )，第2行給出K個整數，中間用空格分隔。當K為0時，輸入結束，該用例不被處理。
輸出：
對每個測試用例，在1行裡輸出最大和、最大連續子序列的第一個和最後一個元素，中間用空格分隔。如果最大連續子序列不唯一，則輸出序號i和j最小的那個（如輸入樣例的第2、3組）。若所有K個元素都是負數，則定義其最大和為0，輸出整個序列的首尾元素。
樣例輸入：
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
樣例輸出：
20 11 13
10 1 4
10 3 5
10 10 10
0 -1 -2
0 0 0
思路
典型的動態規劃的題目，按照動態規劃的解題步驟，首先定義最優解結構，設到第i個數時，最大連續子序列和為sum[i],則sum[i]的遞推公式為：
AC代碼
[cpp]
#include <stdio.h>
#include <stdlib.h>
void max_lcs(int *arr, int n)
{
int begin, end, current, max, i, *sum;
sum = (int *)malloc(sizeof(int) * n);
begin = end = current = 0;
sum[0] = max = arr[0];
for (i = 1; i < n; i ++) {
if (sum[i - 1] >= 0) {
sum[i] = sum[i - 1] + arr[i];
} else {
sum[i] = arr[i];
current = i;
}
if (sum[i] > max) {
max = sum[i];
end = i;
begin = current;
}
}
printf("%d %d %d\n", max, arr[begin], arr[end]);
}
int main(void)
{
int i, n, flag, *arr;
while (scanf("%d", &n) != EOF && n != 0) {
arr = (int *)malloc(sizeof(int) * n);
for (i = 0, flag = 0; i < n; i ++) {
scanf("%d", arr + i);
if (arr[i] >= 0)
flag = 1;
}
if (! flag) { // 均為負數
printf("0 %d %d\n", arr[0], arr[n - 1]);
} else { // 動態規劃
max_lcs(arr, n);
}
free(arr);
}
return 0;
}
/**************************************************************
Problem: 1011
User: wangzhengyi
Language: C
Result: Accepted
Time:10 ms
Memory:1068 kb
****************************************************************/
#include <stdio.h>
#include <stdlib.h>
void max_lcs(int *arr, int n)
{
int begin, end, current, max, i, *sum;
sum = (int *)malloc(sizeof(int) * n);
begin = end = current = 0;
sum[0] = max = arr[0];
for (i = 1; i < n; i ++) {
if (sum[i - 1] >= 0) {
sum[i] = sum[i - 1] + arr[i];
} else {
sum[i] = arr[i];
current = i;
}
if (sum[i] > max) {
max = sum[i];
end = i;
begin = current;
}
}
printf("%d %d %d\n", max, arr[begin], arr[end]);
}
int main(void)
{
int i, n, flag, *arr;
while (scanf("%d", &n) != EOF && n != 0) {
arr = (int *)malloc(sizeof(int) * n);
for (i = 0, flag = 0; i < n; i ++) {
scanf("%d", arr + i);
if (arr[i] >= 0)
flag = 1;
}
if (! flag) { // 均為負數
printf("0 %d %d\n", arr[0], arr[n - 1]);
} else { // 動態規劃
max_lcs(arr, n);
}
free(arr);
}
return 0;
}
/**************************************************************
Problem: 1011
User: wangzhengyi
Language: C
Result: Accepted
Time:10 ms
Memory:1068 kb
****************************************************************/
