How to do this question? Please help

#1

I am applying dynamic programming solution as shown in video but still I am getting TLE. Please guide me how to this question.

#2

See constraints, dynamic programming will definitely give you TLE. It is easy if you think of doing it using map STL or using Binary Index Tree.