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

最大連續子序列

編輯:C++入門知識

[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,輸出整個序列的首尾元素。 
樣例輸入: 

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

5 -8 3 2 5 0 

10 

-1 -5 -2 

-1 0 -2 

樣例輸出: 
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
****************************************************************/

 

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