Discussion @ 1146. Maximum Sum @ Timus Online Judge

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

Posted by SupremeEntropy 25 Jul 2017 20:09

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?

Posted by Mahilewets 25 Jul 2017 23:00

Are you calculating something like "maximal sum subarray" ?
That is where it is DP.

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

Posted by Mahilewets 25 Jul 2017 23:18

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])

Discussion of Problem 1146. Maximum Sum