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.