Leetcode daily # 12.05.2023

[2140. Solving Questions With Brainpower]

12.05.2023

2140. Solving Questions With Brainpower medium

fun mostPoints(questions: Array<IntArray>): Long {
    val dp = LongArray(questions.size)
    for (i in questions.lastIndex downTo 0) {
        val (points, skip) = questions[i]
        val tail = if (i + skip + 1 > questions.lastIndex) 0 else dp[i + skip + 1]
        val notTake = if (i + 1 > questions.lastIndex) 0 else dp[i + 1]
        dp[i] = maxOf(points + tail, notTake)
    }
    return dp[0]
}

blog post

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/210

Intuition

If we go from the tail, for each element we are interested only on what happens to the right from it. Prefix of the array is irrelevant, when we’re starting from the element i, because we sure know, that we are taking it and not skipping.
Given that, dynamic programming equation is:
dpi=max(pointsi+dpi+1+skipi,dpi+1), where dp is the mostPoints starting from position i.

Approach

Let’s implement a bottom-up solution.

Complexity

• Time complexity:
  O(n)

• Space complexity:
  O(n)