UVa 10684 – The jackpot
A person wants to get rich quickly without working too hard, so he decides to make a career in the casino. He starts studying the winning and losing situations of other gamblers so that he can formulate a winning strategy. Since he doesn't understand computers, he hires you to write a program to help him.
Your first task is to write a program to identify the maximum possible winnings in a series of consecutive gambling rounds. Each gambling round is represented by an integer indicating the amount won or lost. Positive numbers represent winnings, while negative numbers represent losses.
For example, if there are 6 rounds of gambling with the following amounts:
-99 10 -9 10 -5 4
The maximum possible winnings in consecutive rounds of gambling are 11, occurring in the second, third, and fourth rounds consecutively.
Sample Inputs/Outputs
Sample Input(s) | Sample Output(s) |
---|---|
EOF inputs: The first line of each test case contains a positive integer N <= 10000, indicating the length of the sequence. Following that are N integers (with absolute values less than 1000), representing the amounts won or lost in the N rounds of gambling. When N = 0, it signifies the end of the input. Please refer to the sample input. | For each test case, output a single line indicating the maximum possible winnings in consecutive rounds of gambling among the N rounds. If it's not possible to win any money based on the input data, output "Losing streak." The output format should follow the format shown in the Sample Output. |
6 -99 10 -9 10 -5 4 3 -999 100 -9 5 12 -4 -10 4 9 3 -2 -1 -2 0 | The maximum winning streak is 11. The maximum winning streak is 100. The maximum winning streak is 13. Losing streak. |
Thought Process
First, store the data in an array. Then, run a for loop to iterate over each possible starting point (i) from i = 0 to i = N-1. Inside this loop, use another for loop to iterate over each possible ending point (j) from j = i to j = N-1, representing the range from the starting point i to the end.
Certainly! You can initialize a variable ans to -9999. Then, every time there is an addition operation, compare it with ans. If the current sum is greater than ans, update ans to the current sum.
Finally, check if ans is greater than 0. If it is, output ans; otherwise, output "Losing streak."
Sample Code-ZeroJudge A540: The jackpot
#include <iostream>
#include <vector>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N;
while (cin >> N && N != 0)
{
vector<int>num;
int ans = -9999;
for (int i = 0; i<N; i++)
{
int tmp;
cin >> tmp;
num.push_back(tmp);
}
for (int i = 0; i<N; i++)
{
int sum = 0;
for (int j = i; j<N; j++)
{
sum += num[j];
ans = max(ans, sum);
}
}
if (ans > 0)
{
cout << "The maximum winning streak is " << ans << ".\n";
continue;
}
cout << "Losing streak.\n";
}
}
//ZeroJudge A540
//Dr. SeanXD