← Static tasks

1043. Partition Array for Maximum Sum

leetcode medium

#array#bit-manipulation#csharp#dynamic-programming#leetcode#math#medium

Task

Если задан целочисленный массив arr, разбейте его на (смежные) подмассивы длины не более k. После разбиения значения каждого подмассива меняются так, чтобы стать максимальным значением этого подмассива. Верните наибольшую сумму заданного массива после разбиения. Тестовые примеры генерируются таким образом, чтобы ответ умещался в 32-битное целое число.

Пример:

Input: arr = [1,15,7,9,2,5,10], k = 3

Output: 84

C# solution

matched/original
public class Solution {
    public int MaxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.Length;
        int[] dp = new int[n];
        
        for (int i = 0; i < n; i++) {
            int maxVal = 0;
            for (int j = 1; j <= k; j++) {
                if (i - j + 1 >= 0) {
                    maxVal = Math.Max(maxVal, arr[i - j + 1]);
                    if (i - j >= 0) {
                        dp[i] = Math.Max(dp[i], dp[i - j] + maxVal * j);
                    } else {
                        dp[i] = Math.Max(dp[i], maxVal * j);
                    }
                }
            }
        }
        
        return dp[n - 1];
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MaxSumAfterPartitioning(vector<int>& arr, int k) {
        int n = arr.size();
        vector<int>& dp = new int[n];
        
        for (int i = 0; i < n; i++) {
            int maxVal = 0;
            for (int j = 1; j <= k; j++) {
                if (i - j + 1 >= 0) {
                    maxVal = max(maxVal, arr[i - j + 1]);
                    if (i - j >= 0) {
                        dp[i] = max(dp[i], dp[i - j] + maxVal * j);
                    } else {
                        dp[i] = max(dp[i], maxVal * j);
                    }
                }
            }
        }
        
        return dp[n - 1];
    }
}

Java solution

matched/original
public class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.length;
        int[] dp = new int[n];
        
        for (int i = 0; i < n; i++) {
            int maxVal = 0;
            for (int j = 1; j <= k; j++) {
                if (i - j + 1 >= 0) {
                    maxVal = Math.max(maxVal, arr[i - j + 1]);
                    if (i - j >= 0) {
                        dp[i] = Math.max(dp[i], dp[i - j] + maxVal * j);
                    } else {
                        dp[i] = Math.max(dp[i], maxVal * j);
                    }
                }
            }
        }
        
        return dp[n - 1];
    }
}

Python solution

matched/original
def maxSumAfterPartitioning(arr, k):
    n = len(arr)
    dp = [0] * n

    for i in range(n):
        max_val = 0
        for j in range(1, k + 1):
            if i - j + 1 >= 0:
                max_val = max(max_val, arr[i - j + 1])
                if i - j >= 0:
                    dp[i] = max(dp[i], dp[i - j] + max_val * j)
                else:
                    dp[i] = max(dp[i], max_val * j)

    return dp[-1]

Go solution

matched/original
func maxSumAfterPartitioning(arr []int, k int) int {
    n := len(arr)
    dp := make([]int, n)
    
    for i := 0; i < n; i++ {
        maxVal := 0
        for j := 1; j <= k; j++ {
            if i - j + 1 >= 0 {
                if arr[i - j + 1] > maxVal {
                    maxVal = arr[i - j + 1]
                }
                if i - j >= 0 {
                    if dp[i] < dp[i - j] + maxVal * j {
                        dp[i] = dp[i - j] + maxVal * j
                    }
                } else {
                    if dp[i] < maxVal * j {
                        dp[i] = maxVal * j
                    }
                }
            }
        }
    }
    
    return dp[n - 1]
}

Explanation

Algorithm

Инициализация:

Создаем массив dp, где dp[i] будет хранить наибольшую сумму подмассива, заканчивающегося в позиции i.

Заполнение массива dp:

Проходим по массиву arr и для каждой позиции i пытаемся разбить подмассив длины до k и обновить dp[i] с максимальной возможной суммой.

Поддержание максимального значения в подмассиве:

Для каждого подмассива длины 1 до k, вычисляем максимальное значение в этом подмассиве и обновляем dp[i].

😎