Oct-28-2021, 09:02 PM
If you have two contiguous slices, a and b, the sum of a + b is only greater than the sum of slice b if the sum of slice a is positive. In other words, the slice with the maximum sum will only start with slice a if the sum of slice a is positive.
In my program subsum is the sum of slice a, and value is the sum of slice b (a slice containing just the next value). The program adds values to slice a, checking if the new sum is the highest sum seen so far. If the sum of slice a is less than zero it is discarded because including a will only decrease the sum of future slices. I also discard a when the sum of a is zero, choosing shorter slices over longer slices of the same value.
This is a good interview question.
In my program subsum is the sum of slice a, and value is the sum of slice b (a slice containing just the next value). The program adds values to slice a, checking if the new sum is the highest sum seen so far. If the sum of slice a is less than zero it is discarded because including a will only decrease the sum of future slices. I also discard a when the sum of a is zero, choosing shorter slices over longer slices of the same value.
This is a good interview question.