I am still learning dp, but the first thing that came to my mind was to use prefix and suffix sums on that problem.