coderadi
BAN USERProgrammer Freak!!
You can do this in O(logN) without finding the max... simply apply a binary searh.. compare the middle element(ar[mid]) with ar[mid-1] and ar[mid+1].. this will determine wether ar[mid] is in the increasing part or decreasing part.. now compare the ar[mid] with the "value".. and switch to the other half accordingly..
It may happen that ar[mid] > both ar[mid-1] & ar[mid+1].. at that point simply call the same binarySearch for both the halfs..
Complexity: O(log N).. every time you will divide the array in half...
example: ar = {6, 20, 15, 12, 11, 10, 9}, length = n
search 11: ar[mid] = 12, ar[mid] > ar[mid+1] && ar[mid] < ar[mid -1] .. so it is decreasing sequence... now 11 < ar[mid].. so call the same method for (mid+1 to n)..
Similarly you can search others..
Simply do a DFS on the tree.. and while doing DFS maintain the current nodes in a stack... when their sum reaches "SUM".. print the stack..
Now you know the logic so it would be better to write the code yourself.. that will help you understand it more clearly... and you will never forget it.. :)
It's a Classical LIS problem.. with a simple addition that we also have to store the LIS so that later we can return it's sum..
Time complexity: O(n^2), Space Complexity: O(n)
- coderadi June 25, 2015