[UVa]10684:The jackpot

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

[C](0.088)

	#include<stdio.h>
	int main()
	{
	int N;
	while( scanf( "%d", &N ) != EOF && N != 0 )
	{
	int money[10005] = {0};
	int dp[10005] = {0}, max = 0;
	int i;
	for( i = 1 ; i <= N ; i++ )
	{
	scanf( "%d", &money[i] );
	if( dp[i-1]+money[i] > money[i] )
	dp[i] = dp[i-1]+money[i];
	else
	dp[i] = money[i];
	max = ( dp[i] > max )? dp[i] : max;
	}
	if( max )
	printf( "The maximum winning streak is %d.\n", max );
	else
	printf( "Losing streak.\n" );
	}
	return 0;
	}

view raw UVa10684.c hosted with ❤ by GitHub