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

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
Top Users 2020 Aug 10 - 16
  1. Arkaprava

    560 Points

  2. jayeshasawa001

    315 Points

  3. SarathBaswa

    288 Points

  4. Ashutosh777

    128 Points

  5. toxicdesire

    53 Points

  6. shashankrustagi2021

    15 Points

  7. Nilabja Sarkar

    12 Points

  8. Mellophi

    11 Points

  9. premu

    10 Points

  10. phaneendrababu

    9 Points

Weekly Top User (excluding moderators) will get free access to GATE Overflow Test Series for GATE 2021
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Aug 2020
  1. Arkaprava

    560 Points

  2. jayeshasawa001

    320 Points

  3. SarathBaswa

    288 Points

  4. Ashutosh777

    204 Points

  5. Mellophi

    161 Points

  6. toxicdesire

    53 Points

  7. anurag sharma

    49 Points

  8. shashankrustagi2021

    25 Points

  9. premu

    16 Points

  10. Shaik Masthan

    16 Points

7,792 questions
2,046 answers
11,376 comments
95,121 users