Hi guys. I just tried to solve the recent ICPC Singapore problem G with DP bottom up. The summary of description is like this :

Given sequence with length N < 3000 with each in range 1 and 10⁹. Find the maximum partition can be made with each sum of partition elements cannot bigger than sum of elements on the right partition

My answer is by make table DP[i, j] contains maximum partition can be made from element [1, j] with last partition covers [i, j]. And then fill the table with DP[i, j] = max{DP[k, i - 1]} + 1 if only Sum_{k, i - 1} ≤ Sum_i, j

My solution

Are there any flaws with my approach?

Any problem with the web now?