資料結構學習筆記——最大子列和問題

PTA

中國大學MOOC-陳越、何欽銘-資料結構

01-複雜度1 最大子列和問題（20 分）

給定K個整數組成的序列{ N​1​​ , N​2​​ , ..., N​k}，“連續子列”被定義為{ N​i , N​i+1​​ , ..., N​j}，其中 1≤i≤j≤K。“最大子列和”則被定義為所有連續子列元素的和中最大者。例如給定序列{ -2, 11, -4, 13, -5, -2 }，其連續子列{ 11, -4, 13 }有最大的和20。現要求你編寫程式，計算給定整數序列的最大子列和。

本題旨在測試各種不同的算法在各種資料情況下的表現。各組測試資料特點如下：

• 資料1：與樣例等價，測試基本正确性；
• 資料2：102個随機整數；
• 資料3：103個随機整數；
• 資料4：104個随機整數；
• 資料5：105個随機整數；

輸入格式:

輸入第1行給出正整數K (≤100000)；第2行給出K個整數，其間以空格分隔。

輸出格式:

在一行中輸出最大子列和。如果序列中所有整數皆為負數，則輸出0。

輸入樣例:

[input]  6
[input]  -2 11 -4 13 -5 -2
           

輸出樣例:

[output] 20
           

思路

1. 輸入要輸入的整數個數

2. 輸入整數

3. 查找最大子列和

>>>> 若序列中所有整數為負數輸出零

4. 輸出

注意

• 步驟三強調

  >>>> 若序列中所有整數為負數輸出零

  , 在程式中表現為當序列和為負數時直接舍去, 務必不能少了此判斷, 否則出錯
• 若步驟二與步驟三分開為兩個循環, 勢必會增加時間複雜度, 将步驟二和三合并于一個循環中, 可以提高算法速度

認真思考, 滿分不難

參考代碼

/*
*@Author: FesonX
*@compiler: C(clang)
*/
#include <stdio.h>

int main()
{
  int K;
  int i = 0;
  int max = 0;
  int temp = 0;
  int a[100000];
  scanf("%d", &K);
  
  while(K--)
  {
    scanf("%d", &a[i]);
    if(temp + a[i] <= 0)
      temp = 0;
    else
      temp = temp + a[i++];
    
    if(temp > max)
      max = temp;
  }
  
  printf("%d", max);
  
  return 0;
}