Frontend School

Maximum Strategic Deployment Profit

DSA
hard

Maximum Strategic Deployment Profit

Hard
Dynamic Programming
1D

Overview

In a competitive resource landscape, Upgrad needs to strategically deploy k specialized units across N potential locations. Each location offers a specific profit, but to maintain operational efficiency and avoid resource conflicts, any two deployed units must be separated by a minimum distance. Your task is to design an algorithm that determines the maximum total profit achievable by deploying exactly k units under these constraints.

What you need to do / Task

  1. Implement the function maxStrategicDeploymentProfit that calculates the maximum total profit.
  2. Your solution should adhere to the given constraints on N, k, min_distance, and values.
  3. Optimize your dynamic programming approach to achieve an efficient time complexity.

Input & output

  • values: An array of integers values[i] representing the profit gained by deploying a unit at location i. values.length is N.
  • k: An integer representing the exact number of units to deploy.
  • min_distance: An integer representing the minimum number of locations that must separate any two deployed units. If units are deployed at indices i and j, then |i - j| > min_distance.
  • Returns: An integer representing the maximum total profit. If it's impossible to deploy k units under the given constraints, return -1.

Clarifications

  • If k is 0, the profit is 0.
  • The condition |i - j| > min_distance means that the difference between indices i and j must be at least min_distance + 1. For example, if min_distance = 0, then |i - j| > 0, meaning i and j must be different. If min_distance = 1, then |i - j| > 1, meaning i and j must be separated by at least one other location (e.g., if a unit is at 0, the next can be at 2 or higher).

Examples

1

Example 1

Input:

values = [10, 5, 20, 15, 25], k = 2, min_distance = 1

Output:

45

Note:

Deploy units at index 2 (profit 20) and index 4 (profit 25). The distance |4 - 2| = 2, which is > min_distance = 1. Total profit = 20 + 25 = 45.

2

Example 2

Input:

values = [1, 2, 3, 4, 5], k = 3, min_distance = 0

Output:

12

Note:

Deploy units at indices 2 (profit 3), 3 (profit 4), and 4 (profit 5). The minimum distance constraint |i - j| > 0 means units must be at different locations. Total profit = 3 + 4 + 5 = 12.

3

Example 3

Input:

values = [10, 20, 30], k = 3, min_distance = 1

Output:

-1

Note:

To deploy 3 units with min_distance = 1, units must be at least 2 positions apart (e.g., indices 0, 2, 4). This requires at least 5 locations. Since N=3, it's impossible to deploy 3 units under these constraints.

Constraints

Constraints & assumptions

  • 1 <= N <= 2000
  • 1 <= k <= N
  • 0 <= min_distance < N
  • -10^5 <= values[i] <= 10^5
  • The sum of values[i] will fit within a standard 32-bit integer range.

What interviewers evaluate

  • Correct identification of a dynamic programming state and recurrence relation.
  • Ability to optimize the DP solution from a naive O(N^2 * K) or O(N * K^2) to O(N * K).
  • Handling edge cases and base conditions correctly (e.g., k=0, impossibility).
  • Code clarity, structure, and readability.

Loading editor...