0 votes 0 votes you are given an array which contain both positive and negative integers in it and asked to design an algorithm to find maximum sum which doest contain twp consecutive numbers .what is the time complexiy of efficient algorithm ? nlogn n2 n n2logn Algorithms algorithms algorithm-design time-complexity + – akankshadewangan24 asked Dec 2, 2017 • edited Jul 6, 2022 by Lakshman Bhaiya akankshadewangan24 823 views answer comment Share Follow See all 9 Comments See all 9 9 Comments reply Anu007 commented Dec 2, 2017 reply Follow Share You didnot give size of elements. 0 votes 0 votes akankshadewangan24 commented Dec 2, 2017 reply Follow Share What if size of the element is n? 0 votes 0 votes akankshadewangan24 commented Dec 2, 2017 reply Follow Share Size is not mentioned in the question . 0 votes 0 votes vamp_vaibhav commented Dec 2, 2017 reply Follow Share Any additional thing whether Array is sorted or initially all positive numbers then negative kind of?? 0 votes 0 votes akshat sharma commented Dec 2, 2017 reply Follow Share It is just like Kadanes algorithm which takes O(n) time for largest sum contiguous Subarray 0 votes 0 votes vamp_vaibhav commented Dec 2, 2017 reply Follow Share #akshat I think kadanes algorithm cannot be applied here.. Because kadanes only allow contiguous subarray.. But here it is explicitly said not to take consecutive values 0 votes 0 votes Rishabh Gupta 2 commented Dec 2, 2017 reply Follow Share I think the best we can do is in nlogn. First, sort it, and then traverse only the positive numbers(just ignore the duplicates while traversing). Other two options are greater than this, so not to consider them. Don't know whether it can be done in n or not. 0 votes 0 votes srivivek95 commented Dec 2, 2017 reply Follow Share @ Rishabh Gupta 2 After sorting how will you preserve the condition that numbers are not consecutive? 0 votes 0 votes Anu007 commented Dec 2, 2017 reply Follow Share Find max element of array. Find 2nd max element of array each time by check no adjacent element taken . by this way we get O(n2) 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes I think in this question apply 2 pass bubble sort which give two largest number which is order of (n) and add two last elements which give constant avadh answered Jun 30, 2018 avadh comment Share Follow See all 0 reply Please log in or register to add a comment.