kashyap2108's blog

Hackerrank-Sherlock And Cost
By kashyap2108, history, 7 years ago, In English

How to solve the question https://www.hackerrank.com/challenges/sherlock-and-cost on hackerrank?

  • Vote: I like it
  • -8
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Some hints:- 1. First come up with a dp with O(n*M*M) where M is the max value of B[i] i.e. 100 2. You don't need to try all values between 1 to B[idx] for some index 'idx'. Only 1 and B[idx] are enough. Now, complexity is O(n*M) 3. Since, you are only trying 1 and B[idx], you can keep a boolean for the previous value you selected. True for B[idx-1] and false for 1.

This changes complexity to O(n*2) = O(n). Final reduced state is (index, isLastValueMax) where isLastValueMax is a Boolean.

→ Reply