#UVa:10684-The jackpot

灆洢 2014-12-23 14:40:49

DP題,利用另外一個陣列記錄到從前面連續到目前這格贏最多的錢是多少,再找這裡面全部最多錢的即是答案。

C++(0.099)

/*******************************************************/
/* UVa 10684 The jackpot                               */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2014/12/23                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
using namespace std;

int main(){
  int N;
  while( scanf("%d", &N ) != EOF && N != 0 ){
    int sequences[10005];
    for( int i = 1 ; i <= N ; ++i ){
      scanf("%d", &sequences[i]);
    }

    int dp[10005] = {0};
    int win = 0;
    for( int i = 1 ; i <= N ; ++i ){
      dp[i] = max( sequences[i], dp[i-1] + sequences[i] );
      win = max( win, dp[i] );
    }

    if( win > 0 ){
      printf("The maximum winning streak is %d.\n", win);
    }
    else{
      printf("Losing streak.\n");
    }
  }
  return 0;
}

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料