22 views

Consider a sequence of 14 elements: A = [-5, -10, 6, 3, -1, -2, 13, 4, -9, -1, 4, 12, -3, 0]. The subsequence sum .

Determine the maximum of S(i,j), where 0 ≤ i ≤ j < 14. (Divide and conquer approach may be used).
Options are :-
a) 19
b) 30
c) 29
d) 9
| 22 views
0
Longest subarray sum can be solved in O(n) using Kadane's algo

U can find several videos on youtube
0
Dirty method if you've forgotten how to apply the algorithm in the exam. This will work if you're really lucky and the array is organized a certain way - i.e. with a run of negative numbers on either end. Will work disastrously if the subarry is in the middle of the array somewhere. So use at your own risk.

-5, -10, 6, 3, -1, -2, 13, 4, -9, -1, 4, 12, -3, 0

Sum everything up : 11.

The idea is to maximize it. Only way to maximize here is to eliminate negative numbers. We have, on either end of the array negative numbers and 0. So straightaway remove all of them

6, 3, -1, -2, 13, 4, -9, -1, 4, 12

Sum everything up : 29.

Think about how you will maximize this. The only possible maximization you can do is by somehow eliminating the negative numbers, which will increase the sum by 1+2+9+1 = 13. BUT, in order to reach those negative numbers - you'll end up losing 6+3+4+12 = 25. Not worth it.

So conclude here, remember your deity of choice in your heart, enter the answer - and think for a moment how nice it would have been if you had remembered the actual algorithm :)
0

So conclude here, remember your deity of choice in your heart, enter the answer - and think for a moment how nice it would have been if you had remembered the actual algorithm :)

MADE MY DAY... XD