The explanation above is correct ... O(n^3) is enough. If you're able to solve the one dimensional array in O(n), then you can solve the 2D case in O(n^3).
For each row-range [a..b], we'll compute the maximum contiguous subarray with the O(n) above. To achieve O(n^3), this means that for each column c, we need to have the sum of arr[a][c], arr[a+1][c], ... arr[b-1][c] handy ( i.e. in O(1) algo). But that's fine, we can precalc them using prefix-sum (O(n^2)). Look at my post in www.algorithmist.com ... search for UVa problem 108 - Maximum Sum. Good luck. On 10/12/07, Andrey <[EMAIL PROTECTED]> wrote: > > > Does anyone knew more effective solution then DP? > > On Oct 12, 3:46 pm, Andrey <[EMAIL PROTECTED]> wrote: > > I doubt It will be O(n^3).. > > Dynamic programming algorithm, by size of submatrix, will give at > > least O(N ^ 4), won't it? > > > > > -- Fear of the LORD is the beginning of knowledge (Proverbs 1:7) --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
