1043. Partition Array for Maximum Sum

LeetCode medium оригинал: C# #array #bit-manipulation #csharp #dynamic-programming #leetcode #math #medium
LeetCode Static

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

Пример:

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

Output: 84

C# решение

сопоставлено/оригинал 
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++ решение

auto-draft, проверить перед отправкой 
#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 решение

сопоставлено/оригинал 
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 решение

сопоставлено/оригинал 
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 решение

сопоставлено/оригинал 
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]
}

Algorithm

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

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

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

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

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

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

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии
Активных вакансий пока нет.