H. Csaba - 1 month ago 4x
C# Question

# subsequence of numbers with maximal sum, solution isn't clear

Write a program, which finds a subsequence of numbers with maximal sum.
E.g.: {2, 3, -6, -1, 2, -1, 6, 4, -8, 8}

The second way is to use one loop through the array to scan it from left to right and sum the elements. Once we get a negative sum, we can
restart summing from the next element. Think why this is correct! At each step we check if the current sum is greater than the current max.

It's not clear to me how is this solution works... Although I solved the problem by another way I can't walk away with that I don't understand this solution... Could you explain it? Thank's for help in advance.

Edit: I solved the task by another way not by what I don't understand :)

Answer

So as you stated, you iterate over the array in one loop and accumulate sum `S`. On each step you do `S += a[i]` and you compare your `S` to current maximum like `max = Math.max(S, a[i])`.

Your question is why should we zero `S` when `S < 0`. Let's say it happened on step `i`. Then `(S + a[i+1]) < a[i+1]` (because S < 0). Since we are looking for maximum subsequent sum its better to start new subsequence from `a[i+1]` i.e. set `S = 0`.

Comments