Efficient Garbage Collection

ArrayGreedyPrefix Sum

You are given an array of integers representing the number of garbage bags collected from each house in a street. Assuming that the garbage truck can collect all the bags from any house without limitation, but it must start collecting from the first house and move to the last without skipping, determine the house number (1-based index) where the garbage truck collects the highest total number of bags cumulatively from the start till that house. If there are multiple houses with the same cumulative amount, return the first such house.

Example 1

Input

[
  1,
  2,
  3,
  4,
  5
]

Output

Explanation. The cumulative sums are [1, 3, 6, 10, 15]. The highest is 15 at house 5.

Example 2

Input

[
  3,
  3,
  3
]

Output

Explanation. All houses give a cumulative of 3, 6, and 9 respectively. House 3 has the highest cumulative sum.

Example 3

Input

[
  10,
  1,
  1,
  10
]

Output

Explanation. The cumulative sums are [10, 11, 12, 22]. The highest cumulative sum starts from house 1 to house 4, being 22.

Example 4

Input

[
  5,
  5,
  10,
  0
]

Output

Explanation. The cumulative sums are [5, 10, 20, 20]. Even though houses 3 and 4 both have a cumulative of 20, the answer is 3 as it's the first.

Follow-up: How would the solution change if the truck could start collecting from any house and move to any other house?

Constraints:

All integers in the input array will be non-negative. The array will contain at least one house.

Views: 2