Hi LC community
had my fist google screening round today . the question was to build an integer which is maximum subsequnce from a subarray of size K. e.g Array is [4 , 9 , 0 , 2] and k = 2. asnwer 92 .
has never seen this before so gave a DP solution with memoization where i add my i'th index number to result and decrement k , or dont add and incremened index. gave TC as k X O(n) . interviewer was not happy asked me to optimized .
I gave an approach wehere i choose from left with atleast k-1 elemet to the right , then again take the max after that index. solved using heap , interviwere agreed but asked to optimize more and even gave a hint which i did not understood . basically i had to use monotonic stack and do it in O(n).
seems this is the end of my google journey for now .
thanks