Участник:ArthurSamuelyan/Partition Array For Maximum Sum

Материал из DISCOPAL
Перейти к: навигация, поиск
class Solution(object):
    def maxSumAfterPartitioning(self, A, K):
        """
        :type A: List[int]
        :type K: int
        :rtype: int
        """
 
        # bestSums[i] - наилучшая сумма после partitionig для A[i:]
        bestSums = [0 for _ in range(len(A)+1)]
 
        for i in range(len(A)-1, -1, -1):
 
            localMax = 0
            for j in range(i, min(i+K, len(A))):
 
                # Находим локальный максимум в partition
                if A[j] > localMax:
                    localMax = A[j]
 
                # Выбираем наилучшую сумму для A[i:] с учетом включения A[j] в partition
                bestSums[i] = max(bestSums[i], (j-i+1) * localMax + bestSums[j+1])
 
        return bestSums[0]