CODEWITHSUNDEEP
arraysalgorithmdata-structuresdynamic-programming
j1119
j1119

Reputation: 143

Maximize sum of array intervals

Given a 2D array with size N, I want to maximize array[0][k1] + array[k1 + 1][k2] + array[k2 + 1][k3] + ... + array[kx + 1][N - 1] for a given x. All k values are strictly increasing.

With small values of x (x = 2, 3, 4), a dynamic programming solution appears feasible.

However, the bound is 1 <= x, N <= 100, so I am not sure how to attempt this.

Upvotes: 1

Views: 89

Answers (1)

Pham Trung
Pham Trung

Reputation: 11294

Assuming that we are at a particular state (ki, xi) with ki is the current k index, x is the last k in order to give the answer for the problem, we need to try to find the maximum value we can create from this state.

We make one observation that the problem can be divided into subproblem (ki, xi). As for each (ki, xi) state, the result is independent of previous state, we can have our formula:

  • For ki == x, answer = 0

  • Otherwise, (ki, xi) = array[xi][z] + max(ki + 1, z) with z > xi

Here is a simple pseudocode

int[][]dp;
boolean[][]check;
boolean maxAmount(int k, int x){
    if(k == X){
       return true;
    }
    if this state is visited {
       return check[k][x];
    } 
    boolean result = false;

    for(int i = x + 1; i < n; i++){
        if(maxAmount(k + 1, i)){
            result = true;
            dp[k][x] = max(dp[k][x], array[x][i] + dp[k + 1][i]);
        }
    }
    return check[k][x] = result;

}

Note: For the special case when we cannot find enough k, you need to handle it depending on the requirement, but it should be trivial.

Upvotes: 2

Related Questions