Maximize the sum of maximum elements of at least K-sized subarrays
Given an integer array arr[] of length N and an integer K, partition the array in some non-overlapping subarrays such that each subarray has size at least K and each element of the array should be part of a subarray. The task is to maximize the sum of maximum elements across all the subarrays.
Examples:
Input: N = 4 , K = 1, arr[] = {1, 2, 3, 4}
Output: 10
Explanation: The most optimal way of partition is {1}, {2}, {3}, {4} and total score is 1 + 2 + 3 + 4 = 10Input: N = 6, K = 2, arr[] = {1, 2, 9, 8, 3, 4}
Output: 17
Explanation: The most optimal way of partition is {1, 2, 9}, {8, 3, 4} and total score is max({1, 2, 9}) + max({8, 3, 4}) = 9 + 8 = 17
Approach: To solve the problem, follow the below idea:
The idea in this is to explore all the combinations of subarrays possible which have a size of at least K. We can do this using recursion and explore every possibility. For every index, we have two choices: Either add the current element to the partition or start a new partition from this index. Explore both the choices on each index to maximize the sum of maximum elements of all subarrays.
Step-by-step algorithm:
- Declare a recursive function solve() that takes the current index idx, the minimum subarray length K, and the input array arr.
- Base case is if the idx is greater than equal to the size of the array then we return 0.
- If arr.size()-idx is less than K then we return -1e5.
- Initialize a variable maxi equal to -1 and cnt equal to 0 and ans equal to -1.
- Run a loop j from idx to arr.size().
- Increase cnt by 1 and check if arr[j] > maxi then update maxi to arr[j] and maxi.
- If the cnt is greater than or equal to K then call the solve() function for j+1 and add maxi to it and update the ans to the maximum of ans and the sum of maxi and value returned by recursive function.
- Return ans.
Below is the implementation of the algorithm:
#include <bits/stdc++.h>
using namespace std;
// Function to iterate in the given array
long long dpf(int i, int K, vector<int>& arr)
{
// If length of array is reached
if (i >= arr.size())
return 0;
// If left array size is less than K
if (arr.size() - i < K)
return -1e15;
int maxi = -1;
int cnt = 0;
long long ans = -1;
// Iterate in array
for (int j = i; j < arr.size(); j++) {
// Update the array
maxi = max(arr[j], maxi);
cnt++;
if (cnt >= K)
ans = max(ans, maxi + dpf(j + 1, K, arr));
}
// Return the maximum score
return ans;
}
// Function to find maximum score
long long MaximumScore(int N, int K, vector<int>& arr)
{
// Function call to iterate
return dpf(0, K, arr);
}
// Driver code
int main()
{
int N = 4;
int K = 1;
vector<int> arr = { 1, 2, 3, 4 };
// Function call
cout << MaximumScore(N, K, arr);
return 0;
}
import java.util.ArrayList;
public class Main {
// Function to iterate in the given array
static long dpf(int i, int K, ArrayList<Integer> arr) {
// If length of array is reached
if (i >= arr.size())
return 0;
// If left array size is less than K
if (arr.size() - i < K)
return Long.MIN_VALUE;
int maxi = -1;
int cnt = 0;
long ans = Long.MIN_VALUE;
// Iterate in array
for (int j = i; j < arr.size(); j++) {
// Update the array
maxi = Math.max(arr.get(j), maxi);
cnt++;
if (cnt >= K)
ans = Math.max(ans, maxi + dpf(j + 1, K, arr));
}
// Return the maximum score
return ans;
}
// Function to find maximum score
static long MaximumScore(int N, int K, ArrayList<Integer> arr) {
// Function call to iterate
return dpf(0, K, arr);
}
// Driver code
public static void main(String[] args) {
int N = 4;
int K = 1;
ArrayList<Integer> arr = new ArrayList<Integer>() {{
add(1);
add(2);
add(3);
add(4);
}};
// Function call
System.out.println(MaximumScore(N, K, arr));
}
}
// This code is contributed by akshitaguprzj3
// C# program for the above approach
using System;
using System.Collections.Generic;
public class MainClass {
// Function to iterate in the given array
public static long Dpf(int i, int K, List<int> arr)
{
// If length of array is reached
if (i >= arr.Count)
return 0;
// If left array size is less than K
if (arr.Count - i < K)
return int.MinValue;
int maxi = int.MinValue;
int cnt = 0;
long ans = int.MinValue;
// Iterate in array
for (int j = i; j < arr.Count; j++) {
// Update the array
maxi = Math.Max(arr[j], maxi);
cnt++;
if (cnt >= K)
ans = Math.Max(ans,
maxi + Dpf(j + 1, K, arr));
}
// Return the maximum score
return ans;
}
// Function to find maximum score
public static long MaximumScore(int N, int K,
List<int> arr)
{
// Function call to iterate
return Dpf(0, K, arr);
}
// Driver code
public static void Main(string[] args)
{
int N = 4;
int K = 1;
List<int> arr = new List<int>{ 1, 2, 3, 4 };
// Function call
Console.WriteLine(MaximumScore(N, K, arr));
}
}
// This code is contributed by Susobhan Akhuli
// Function to find maximum score
function maximumScore(N, K, arr) {
// Function to iterate in the given array
function dpf(i, K, arr) {
// If length of array is reached
if (i >= arr.length)
return 0;
// If left array size is less than K
if (arr.length - i < K)
return Number.MIN_SAFE_INTEGER;
let maxi = -1;
let cnt = 0;
let ans = Number.MIN_SAFE_INTEGER;
// Iterate in array
for (let j = i; j < arr.length; j++) {
// Update the array
maxi = Math.max(arr[j], maxi);
cnt++;
if (cnt >= K)
ans = Math.max(ans, maxi + dpf(j + 1, K, arr));
}
// Return the maximum score
return ans;
}
// Function call to iterate
return dpf(0, K, arr);
}
// Driver code
function main() {
const N = 4;
const K = 1;
const arr = [1, 2, 3, 4];
// Function call
console.log(maximumScore(N, K, arr));
}
// Calling the main function to execute the code
main();
# Python program for the above approach
# Function to iterate in the given array
def dpf(i, K, arr):
# If length of array is reached
if i >= len(arr):
return 0
# If left array size is less than K
if len(arr) - i < K:
return -1e15
maxi = -1
cnt = 0
ans = -1
# Iterate in array
for j in range(i, len(arr)):
# Update the array
maxi = max(arr[j], maxi)
cnt += 1
if cnt >= K:
ans = max(ans, maxi + dpf(j + 1, K, arr))
# Return the maximum score
return ans
# Function to find maximum score
def MaximumScore(N, K, arr):
# Function call to iterate
return dpf(0, K, arr)
# Driver code
if __name__ == "__main__":
N = 4
K = 1
arr = [1, 2, 3, 4]
# Function call
print(MaximumScore(N, K, arr))
# This code is contributed by Susobhan Akhuli
Output
10
Time Complexity: O(N * K), where N is the size of input array arr[] and K is the minimum size of each subarray.
Auxiliary Space: O(1)
Contact Us