LC-3077 Hard LeetCode

3077. Maximum Strength of K Disjoint Subarrays

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 27% Topics: Array, Dynamic Programming, Prefix Sum

Reading material

Arrays & Hashing 12 min 1-D Dynamic Programming 16 min Prefix Sums & Difference Arrays 11 min

Reference solution (spoiler · python)

# Time:  O(k * n)
# Space: O(n)

# dp, greedy, kadane's algorithm
class Solution(object):
    def maximumStrength(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        dp = [0]*(len(nums)+1)
        for i in xrange(k):
            new_dp = [float("-inf")]*(len(nums)+1)
            for j in xrange(len(nums)):
                new_dp[j+1] = max(new_dp[j], dp[j])+nums[j]*(k-i)*(1 if i%2 == 0 else -1)
            dp = new_dp
        return max(dp)


# Time:  O(k * n)
# Space: O(k * n)
# dp, greedy, kadane's algorithm
class Solution2(object):
    def maximumStrength(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        dp = [[float("-inf")]*(len(nums)+1) for _ in xrange(k+1)]
        dp[0] = [0]*(len(nums)+1)
        for i in xrange(k):
            for j in xrange(len(nums)):
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j])+nums[j]*(k-i)*(1 if i%2 == 0 else -1)
        return max(dp[-1])

Solution from kamyu104/LeetCode-Solutions · MIT