Loading...
Loading...
Loading...
A tea stall owner writes down the profit of each day; a loss is a negative number. Find the largest total profit of one or more consecutive days. If every day was a loss, the answer is the smallest loss.
Example 1
Input
8 -2 1 -3 4 -1 2 1 -5
Output
6
Days 4 to 7: 4 - 1 + 2 + 1 = 6.
Example 2
Input
3 -8 -3 -6
Output
-3
Every day is a loss; the best stretch is the single day with -3.
Try the problem first. Open one hint at a time.
For each day, find the best stretch that ends on that day.
That best stretch is either the day alone, or the best stretch ending yesterday plus today: take the larger.
The answer is the largest of these values. Use long.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor