Is O(n^3) solution - DP one?

Solution looks like bruteforce with a precalc, not a dynamic programming one. Or precalc counts as DP? Or DP is just a clever bruteforce?

*Edited by author 25.07.2017 20:10*

Re: Is O(n^3) solution - DP one?

Are you calculating something like "maximal sum subarray" ?

That is where it is DP.

Re: Is O(n^3) solution - DP one?

If you are doing Kadane algorithm

You are doing essentially that thing

dp[i] = max(0, dp[i-1] + matrix [i])

answer = max(dp[i])