23.06.10 Today’s Leetcode

1802. Maximum Value at a Given Index in a Bounded Array (medium)

DFS Approach : failed at 20

class Solution:
    def maxValue(self, n: int, index: int, maxSum: int) -> int:
        def dfs(size, value, target, cur, prev):
            if cur < 0:
                return -1
            if value > maxSum:
                return -1
            if size == n:
                return target 
            
            temp = 0
            for i in [-1, 0, 1]:
                next_ = cur + i
                target = next_ if size == n - 1 or target >= 0 else target
                temp = max(temp, dfs(size + 1, value + next_, target, next_, cur))
            return temp
        
        return dfs(0, 0, -1, 1, 0)

mathematical Approach.

class Solution:
    def maxValue(self, n: int, index: int, maxSum: int) -> int:
        def cal(a, b):
            return a * (a + 1) // 2 - b * (b + 1) // 2
        
        res = maxSum // n

        for cur in range(maxSum // n, maxSum):
            left = cal(cur, cur - index - 1)
            right = cal(cur, n - index - 1)
            if left + right + cur < maxSum:
                res = max(res, cur)
        
        return res
            
        

mathematical Approach with Binary Search

class Solution:
    def check(self, a):
        left_offset = max(a - self.index, 0)
        result = (a + left_offset) * (a - left_offset + 1) // 2
        right_offset = max(a - ((self.n - 1) - self.index), 0)
        result += (a + right_offset) * (a - right_offset + 1) // 2
        return result - a

    def maxValue(self, n, index, maxSum):
        self.n = n
        self.index = index

        maxSum -= n
        left, right = 0, maxSum
        while left < right:
            mid = (left + right + 1) // 2
            if self.check(mid) <= maxSum:
                left = mid
            else:
                right = mid - 1
        result = left + 1
        return result