data structure

Question

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

Comments

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.

---

@ Rishabh Gupta 2 After sorting how will you preserve the condition that numbers are not consecutive?

---

Find max element of array. 

Find 2^nd max element of array each time by check no adjacent element taken .

by this way we get O(n²)

Answer 1

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