# 14.05.2023 [1799. Maximize Score After N Operations]

14.05.2023

1799. Maximize Score After N Operations hard
blog post
substack

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/212

Problem TLDR

Max indexed-gcd-pair sum from 2n array; [3,4,6,8] -> 11 (1gcd(3,6) + 2gcd(4,8))

Intuition

For each step and remaining items, the result is always the same, so is memorizable.

Approach

• search all possible combinations with DFS

• use bitmask to avoid double counting

• use an array for cache

Complexity

• Time complexity:
  O(n^2 2^n)

• Space complexity:
  O(n^2 2^n)

Code

    fun gcd(a: Int, b: Int): Int = if (b % a == 0) a else gcd(b % a, a)
    fun maxScore(nums: IntArray): Int {
        val n = nums.size / 2
        val cache = Array(n + 1) { IntArray(1 shl nums.size) { -1 } }
        fun dfs(step: Int, mask: Int): Int {
            if (step > n) return 0
            if (cache[step][mask] != -1) return cache[step][mask]
            var max = 0
            for (i in 0..nums.lastIndex) {
                val ibit = 1 shl i
                if (mask and ibit != 0) continue
                for (j in (i + 1)..nums.lastIndex) {
                    val jbit = 1 shl j
                    if (mask and jbit != 0) continue
                    val curr = step * gcd(nums[i], nums[j])
                    val next = dfs(step + 1, mask or ibit or jbit)
                    max = maxOf(max, curr + next)
                }
            }
            cache[step][mask] = max
            return max
        }
        return dfs(1, 0)
    }