DP is an overkill for this problem


#1

Can be solved in O(n) time and O(1) space.