Linear Sequence

In general, the problems under this category fall under a similar problem scope as Perfect Squares where the optimal answer can usually acquired by solving for every prefix/suffix of the array and then using the previously computed past states to compute the current state.

This is a combination of the trick to "re-frame the problem" and the recurrence pattern of "past states".