Участник:Rimon/Maximum Sum of 3 Non-Overlapping Subarrays

Материал из DISCOPAL
< Участник:Rimon
Версия от 11:59, 27 ноября 2020; Rimon (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/

 
class Solution:
    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
        M = 3
        N = len(nums)
        dp = [[0] * N for _ in range(M)]
        idx = [[''] * N for _ in range(M)] 
        if len(nums) < (k * M): return ans        
 
        for m in range(M):
            sum_win = None
            for n in range(N):
                if n >= m * k:
 
                    if sum_win is None:  
                        sum_win = sum(nums[n-k+1:n+1])
                    else:
                        if n-k >= 0:
                            sum_win += (nums[n] - nums[n-k])
                        else:
                            sum_win = sum(nums[n-k+1:n+1])
 
 
                    new_val = sum_win + dp[m-1][n-k]
                    pre_val = dp[m][n-1]
                    if new_val > pre_val:
                        dp[m][n] = sum_win + dp[m-1][n-k]
                        if len(idx[m-1][n-k]) > 0:
                            idx[m][n] = idx[m-1][n-k] + "," + "%s" % str(n-k+1)
                        else:
                            idx[m][n] = "%s" % str(n-k+1)
                    else:
                        dp[m][n] = dp[m][n-1]
                        idx[m][n] = idx[m][n-1]
 
        tmp = idx[m][n]
        return eval("[%s]" % re.sub(",+", ',', tmp))