Maximum Strength of K Disjoint Subarrays - Practice Coding Problems

Maximum Strength of K Disjoint Subarrays - Problem

You are given an array of integers nums with length n, and a positive odd integer k.

Select exactly k disjoint subarrays sub₁, sub₂, ..., subₖ from nums such that the last element of subᵢ appears before the first element of subᵢ₊₁ for all 1 ≤ i ≤ k-1.

The goal is to maximize their combined strength. The strength of the selected subarrays is defined as:

strength = k × sum(sub₁) - (k-1) × sum(sub₂) + (k-2) × sum(sub₃) - ... - 2 × sum(subₖ₋₁) + sum(subₖ)

where sum(subᵢ) is the sum of the elements in the i-th subarray.

Return the maximum possible strength that can be obtained from selecting exactly k disjoint subarrays from nums.

Note: The chosen subarrays don't need to cover the entire array.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,5,-3,2,4], k = 3

› Output: 13

💡 Note: Select subarrays [1], [-3], [4]. Strength = 3×1 - 2×(-3) + 1×4 = 3 + 6 + 4 = 13

Example 2 — Longer Subarrays

$ Input: nums = [5,-2,3,1], k = 1

› Output: 35

💡 Note: Select subarray [5,-2,3,1] with sum 7. Strength = 1×7 = 7. Wait, this should be 5×1 = 5 for just [5]. Actually, best is [5,-2,3,1] = 7

Example 3 — Minimum k

$ Input: nums = [8,-4], k = 1

› Output: 8

💡 Note: Select subarray [8]. Strength = 1×8 = 8

Constraints

1 ≤ nums.length ≤ 10⁴
1 ≤ k ≤ nums.length
k is odd
-10⁹ ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,5,-3,2,4] with k=3 subarrays needed

Selection

Choose 3 disjoint subarrays with weights 3, -2, 1

Calculation

Strength = 3×1 - 2×(-3) + 1×4 = 13

Key Takeaway

🎯 Key Insight: The alternating weight pattern means we want maximum positive subarrays for odd positions and minimum (most negative) for even positions

Asked in

G Google 35 f Meta 28 a Amazon 22

The key insight is using dynamic programming to track maximum strength achievable with exactly i subarrays. The alternating weight pattern (positive for odd positions, negative for even) requires careful state management. Best approach uses 2D DP with prefix sums for efficient subarray sum calculation. Time: O(n³×k), Space: O(n×k)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(n^(2k))	O(k)	Generate all possible combinations of k disjoint subarrays and calculate their strength
Dynamic Programming with State Tracking	O(n³ × k)	O(n × k)	Use 2D DP where dp[i][j] represents maximum strength with i subarrays ending at or before position j

Brute Force - Try All Combinations — Algorithm Steps

Generate all possible combinations of k disjoint subarrays
For each combination, calculate the strength using the given formula
Return the maximum strength found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Generate all possible combinations of k disjoint subarrays

Calculate

Calculate strength for each combination using weighted formula

Maximum

Return the maximum strength found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

long long maxStrength = LLONG_MIN;

void backtrack(int* nums, int numsSize, int pos, int* selected, int selectedSize, long long currentStrength, int k) {
    if (selectedSize == k) {
        if (currentStrength > maxStrength) {
            maxStrength = currentStrength;
        }
        return;
    }
    if (pos >= numsSize || selectedSize + (numsSize - pos) < k) {
        return;
    }
    
    for (int start = pos; start < numsSize; start++) {
        for (int end = start; end < numsSize; end++) {
            long long subarraySum = 0;
            for (int i = start; i <= end; i++) {
                subarraySum += nums[i];
            }
            int weight = k - selectedSize;
            if (selectedSize % 2 == 1) {
                weight = -weight;
            }
            long long newStrength = currentStrength + (long long)weight * subarraySum;
            selected[selectedSize * 2] = start;
            selected[selectedSize * 2 + 1] = end;
            backtrack(nums, numsSize, end + 1, selected, selectedSize + 1, newStrength, k);
        }
    }
}

long long solution(int* nums, int numsSize, int k) {
    maxStrength = LLONG_MIN;
    int* selected = (int*)malloc(k * 2 * sizeof(int));
    backtrack(nums, numsSize, 0, selected, 0, 0, k);
    free(selected);
    return maxStrength;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    int nums[1000], numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    int k;
    scanf("%d", &k);
    printf("%lld\n", solution(nums, numsSize, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n^(2k))

For each subarray, we try all possible start and end positions, leading to exponential combinations

✓ Linear Growth

Space Complexity

O(k)

Space needed to store the current combination of k subarrays

✓ Linear Space

23.1K Views

Medium Frequency

~35 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler