Find largest sum not involving consecutive values

Question

There is a question to basically find the largest sum in an array, such that no two elements are chosen adjacent to each other. The concept is to recursively calculate the sum, while considering and not considering every element, and skipping an element depending on whether the previous element was selected or not.

I understand that this problem requires the use of Dynamic Programming, but doing so still gives me a TLE. Although my code is very similar to the solution code, I cannot figure out why am I getting a TLE (>1.9 seconds). The constraints are given that n >= 1, and so initialising the DP array to 0's shouldn't be a problem in my opinion.

Algorithmically, I think that the two codes below achieve the same task: processing each element, then either considering it in the sum (in this case, the next recursive call is done for the (i+2)th element), or not considering the element in the sum (the next recursive call is done for the (i+1)th element.

Note:

• vector<int>&B -> denotes the array elements.
• int K -> denotes the number of elements whose sum is to be taken
• int N -> total number of elements in the vector.
• int i -> keep track of which element is currently being processed

Here is my code:

class Solution{
public:
long long dp[1010][510];
long long maxSum(vector<int> &B, int K, int N, int i){
    if (K == 0) return 0;
    else if(i >= N){
        return INT_MIN;
    }
    else{
        if (dp[i][K] != INT_MIN) return dp[i][K];
        dp[i][K] = max(maxSum(B, K, N, i+1), B[i] + maxSum(B, K-1, N, i+2));
        return dp[i][K];
    }
}

long long maximumBeauty(int N, int K, vector<int> &B){
    int i = 0;
    for (int i = 0; i<1010; i++){
        for (int j = 0; j<510; j++){
            dp[i][j] = INT_MIN;
        }
    }
    return maxSum(B, K, N, i);
}
};

and here is the given solution:

class Solution{
public:
long long dp(int i, int j, int N, int K, vector<int> &B,
             vector<vector<long long>> &cache){
    if(j >= K){
        return 0;
    }
    if(i >= N){
        return -1e15;
    }
    if(cache[i][j] != -1e18){
        return cache[i][j];
    }
    cache[i][j] = max((long long )B[i] + dp(i + 2, j + 1, N, K, B, cache),
                      dp(i + 1, j, N, K, B, cache));
    return cache[i][j];
}

long long maximumBeauty(int N, int K, vector<int> &B){
    vector<vector<long long>> cache(N, vector<long long> (K, -1e18));
    long long ans = dp(0, 0, N, K, B, cache);
    return ans;
}
};

I've tried initialising the DP array to different values (such as initialising it with INT_MIN's instead of 0's), but I'm still getting a TLE. Please help me figure out the reason for getting a TLE in the first code, while the second code does not.

EDIT If you want to test the code out and whether it's giving a TLE error, you can try submitting the code here: question-link

Answer 1

Do the math to fix a bug

INT_MIN is not an appropriate value to return when the end of the array is reached (i >= N). It's not low enough!

Given the constraints:

• \$1 ≤ N ≤ 1000\$
• \$1 ≤ K ≤ ceil(N / 2)\$
• \$1 ≤ B[i] ≤ 10^9\$

The biggest sum could reach \$10^9 * 500 = 500000000000\$.

reachable sum = 500000000000
INT_MIN       =  -2147483648 (in this competition environment)

And given that the code has this:

if (i >= N) return INT_MIN;

This leads to problems. The intention at this point in the code is to stop exploring this branch of computations, because we're off the end of the input array, so no solutions could possibly come out of this.

Consider this valid input:

7 4
1 1000000000 1 1000000000 1 1000000000 1

The only way to pick 4 non-adjacent items is to pick 1 + 1 + 1 + 1 = 4.

The alternative path computed by the code is intended to be 1000000000 + 1000000000 + 1000000000 + IMPOSSIBLE.

But since "IMPOSSIBLE" is actually -2147483648, the program incorrectly computes as the solution 1000000000 + 1000000000 + 1000000000 + -2147483648 = 852516352.

The fix is simple: define const long long IMPOSSIBLE = -1e9 * 500, and use that instead of INT_MIN.

Allocate memory precisely

The program allocates memory for the dp array to hold computation results of sub-problems:

long long dp[1010][510];

The array dimensions don't match well the listed constraints. The numbers look like something I used to lazily pick, thinking along the lines of "that's gotta be enough to save me from off-by-one errors". Later in life I realized it's worth forcing myself to think the math through.

What the program needs at most is really "just":

long long dp[1000][500];

This will force you to think through potential off-by one errors, and realize that the program needs some minor adjustments.

But the main point here is not about the numbers, but about the process. Because by thinking these numbers through, now I'm more aware of any excess, and it turns out to be important: the program allocates a 500k array for every input, regardless of its size.

And as it turns out, replacing the fixed storage with dynamic storage that's just right for the input makes the solution fast enough to pass.

Other notes

I understand that this problem requires the use of Dynamic Programming, but doing so still gives me a TLE.

Yes. Using the right approach is often not enough. It's important to use it the right way, and to avoid wasting memory and unnecessary computations.

I've tried initialising the DP array to different values (such as initialising it with INT_MIN's instead of 0's), but I'm still getting a TLE.

The initial values are important for logical reasons, not the performance. The algorithm needs to be able to decide if a value is unset or not. Given the input constraints, any value that will never be a valid sum, for example -1 would work.

Alternative implementation

Based on the above, and some other minor improvements, this is a slightly cleaner, passing version of your solution:

class Solution {
public:
const long long IMPOSSIBLE = -1e9 * 500;
const long long UNSET = -1;

long long maxSum(int i, int k, int N, vector<int> &B, vector<vector<long long>> &dp) {
    if (k == 0) return 0;

    if (i >= N) return IMPOSSIBLE;

    if (dp[i][k - 1] != UNSET) return dp[i][k - 1];
    
    dp[i][k - 1] = max(maxSum(i+1, k, N, B, dp), B[i] + maxSum(i+2, k-1, N, B, dp));
    
    return dp[i][k - 1];
}

long long maximumBeauty(int N, int K, vector<int> &B) {
    vector<vector<long long>> cache(N, vector<long long> (K, UNSET));
    return maxSum(0, K, N, B, cache);
}
};

Answer 2

Algorithmically ... the two codes below achieve the same task

No.

    if(i >= N){
        return -1e15;
    }
    if(cache[i][j] != -1e18){

The "given" solution distinguishes between two very small numbers, while yours uses only INT_MIN.

---

retain order

Your identifiers are very short, single-character. Perhaps that's necessary, based on how the original problem was phrased, fine.

long long maximumBeauty(int N, int K, vector<int> &B){
...
    return maxSum(B, K, N, i);

But don't arbitrarily reorder {N, K, B} to {B, K, N}, that's crazy. Though the machine doesn't care, you're not helping with human cognition.

Copying identifier names was good. But you should have included comments describing the meaning behind each single-character name.

---

This codebase accomplishes a subset of its design goals.

I would not be willing to delegate or accept maintenance tasks on it.