A communication link is established between Cox’s Bazar and Kuakata through n intermediate stations, M₁, M₂, …, Mₙ, arranged in order along the…

A communication link is established between Cox’s Bazar and Kuakata through n intermediate stations, M₁, M₂, …, Mₙ, arranged in order along the route. The distance between each pair of consecutive stations Mᵢ and Mᵢ₊₁ is Pᵢ > 0, for 1 ≤ i < n. At most one repeater can be installed at each intermediate station, and any two selected repeater stations must be at least K kilometers apart.

Using Dynamic Programming, develop an algorithm to determine the maximum number of repeaters that can be installed while satisfying the minimum-distance constraint. Write the pseudocode and analyze its time and space complexity.

Assumption: Repeaters can be installed only at the intermediate stations; Cox’s Bazar and Kuakata are not eligible for repeater installation.

Algorithm MaxRepeaters(P, n, K)
    // Step 1: Calculate station positions
    x[1] = 0
    for i = 2 to n do
        x[i] = x[i - 1] + P[i - 1]

    // Step 2: Initialize DP array
    DP[0] = 0

    // Step 3: Find the maximum number of repeaters
    for i = 1 to n do
        DP[i] = DP[i - 1]       // Skip station i

        for j = i - 1 downto 1 do
            if x[i] - x[j] >= K then
                DP[i] = max(DP[i], DP[j] + 1)
                break

        DP[i] = max(DP[i], 1)

    return DP[n]


Time Complexity: O(n^2)
Space Complexity: O(n)