Awesome q2a theme
0 votes
11 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
ago in Algorithms by (6 points) | 11 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

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Jan 2020
  1. shashin

    1163 Points

  2. Vimal Patel

    306 Points

  3. Deepakk Poonia (Dee)

    305 Points

  4. Debapaul

    237 Points

  5. Satbir

    192 Points

  6. SuvasishDutta

    137 Points

  7. Pratyush Priyam Kuan

    118 Points

  8. tp21

    108 Points

  9. pranay562

    95 Points

  10. DukeThunders

    94 Points

Monthly Top User and those within 60% of his/her points will get a share of monthly revenue of GO subject to a minimum payout of Rs. 500. Current monthly budget for Top Users is Rs. 75.
2,983 questions
1,509 answers
8,931 comments
89,814 users