Ya , because an Input array with all items are positive is a special case, the algorithm must return the whole array
it's hard to work with an array with negative elements inside
I know , but in this question we want consecutive items, 5 and 10 are not, it's not a { } set it's [ ], so we care about ordering
in my example , I can't get [1,-4] for example
got it ?
No problem, I also didn't get the idea when I heard about it
let's take for example this array ( [1,-2,3,-4]) what's the consecutive subsets ( subarrays ) which we can derive from it, and their sums
[1] = 1 [1,-2] = -1 [1,-2,3] = 2 [1,-2,3,-4] = 2- [-2] = -2 [-2,3] = 1 .. [3] = 3 [3,-4] = -1
[-4]
so, the algorithm must return the subarray [3] which has the biggest sum which is 3
more examples ?
Hello I'm thinking in a way, but I don't know if it can be implemented in O(n) way
first, we take the integral of the array for example A = [1,2,3,4,5] would give us the integral B = [1,2,6,10,15]
then we shall find the maximum difference between two items in this integral, such that the maximum index > minimum index
and these indexes ( indices ) are the first and end of the maximum subset
does that make sense ?
