LeetCode Entry
3225. Maximum Score From Grid Operations
Max sum adjacent to marked columns
3225. Maximum Score From Grid Operations hard substack youtube
https://dmitrysamoylenko.com/leetcode/
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/1343
Problem TLDR
Max sum adjacent to marked columns
Intuition
Didn’t solve.
// looks like DP
// at each column peek the best index, n^2 args and n inside = n^3
// how to add previous white when doing current black and not overcount
// 17 minute: my result is too much / too little
// meaning: my dp cases are wrong
// 1:18: TLE, O(n^4) solution
//
The O(n^4) idea: consider previous-previous(PP), previous(P) and the current (C) columns. Peek the best C to maximize sum of previous. Use prefix sums of columns, result = max(PS(max(C,PP)) - PS(P)) The O(n^3) idea jump from n^4: submit to hard rule: can we take values from the current column or should we skip them. That allows to drop PP.
Approach
- the idea jump is not obvious, requires graphic visualizaition of possible outcomes
Complexity
-
Time complexity: \(O(n^3)\)
-
Space complexity: \(O(n^2)\)
Code
fun maximumScore(g: Array<IntArray>): Long {
val dp = HashMap<Int, Long>(); val ps = Array(g.size+1){LongArray(g.size+1)}
for (x in g.indices) for (y in 1..g.size) ps[x+1][y] += ps[x+1][y-1]+g[y-1][x]
fun dfs(i: Int, p: Int, skip: Int):Long = if (i==g.size)0L else dp.getOrPut(i*400+p*2+skip) {
(0..g.size).maxOf { j ->
val a = dfs(i+1, j, 0); val b = dfs(i+1, j, 1)
if (skip > 0 && j > p) ps[i][j]-ps[i][p] + max(a, b)
else if (skip < 1 && j <= p) max(ps[i+1][p]-ps[i+1][j] + a, b) else 0L
}}
return max(dfs(0, 0, 0),dfs(0,0,1))
}