Maximum Total Reward Using Operations I - Practice Coding Problems

Maximum Total Reward Using Operations I - Problem

You are given an integer array rewardValues of length n, representing the values of rewards. Initially, your total reward x is 0, and all indices are unmarked.

You are allowed to perform the following operation any number of times:

Choose an unmarked index i from the range [0, n - 1].
If rewardValues[i] is greater than your current total reward x, then add rewardValues[i] to x (i.e., x = x + rewardValues[i]), and mark the index i.

Return an integer denoting the maximum total reward you can collect by performing the operations optimally.

Input & Output

Example 1 — Basic Case

$ Input: rewardValues = [1,1,3,3]

› Output: 4

💡 Note: Sort to [1,1,3,3]. Start with total=0. Select first 1 (1>0), total=1. Skip second 1 (1≤1). Select first 3 (3>1), total=4. Skip second 3 (3≤4). Maximum reward is 4.

Example 2 — All Selectable

$ Input: rewardValues = [1,6,4,3,2]

› Output: 11

💡 Note: Sort to [1,2,3,4,6]. Start with total=0. Select 1 (total=1), select 2 (total=3), select 3 (total=6), skip 4 (4≤6), skip 6 (6≤6). Maximum reward is 6.

Example 3 — Single Element

$ Input: rewardValues = [5]

› Output: 5

💡 Note: Only one element [5]. Since 5 > 0, we can select it. Maximum reward is 5.

Constraints

1 ≤ rewardValues.length ≤ 2000
1 ≤ rewardValues[i] ≤ 2000

Visualization

Tap to expand

Understanding the Visualization

Input

Array of reward values [1,1,3,3]

Process

Sort and greedily select rewards > current total

Output

Maximum total reward achievable: 4

Key Takeaway

🎯 Key Insight: Sort rewards and greedily select each reward that's greater than current total to maximize the final sum

Asked in

M Meta 15 a Amazon 12 M Microsoft 8

The key insight is to sort the rewards and use a greedy approach. Start with total reward 0, then iterate through sorted rewards and select each reward only if it's greater than the current total. This maximizes the number of rewards we can collect. Best approach is Greedy with Sorting: Time O(n log n), Space O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming with Memoization	O(n × 2ⁿ × S)	O(2ⁿ × S)	Use memoization to avoid recalculating the same states
Greedy with Sorting	O(n log n)	O(1)	Sort rewards and greedily select the largest possible reward at each step
Brute Force Recursion	O(2ⁿ)	O(n)	Try all possible sequences of selecting rewards

Dynamic Programming with Memoization — Algorithm Steps

Define state as (currentReward, usedMask)
Use memoization to cache computed states
Avoid redundant calculations

Visualization

Tap to expand

Step-by-Step Walkthrough

First Computation

Calculate result for state (reward, usedMask)

Cache Result

Store result in memoization table

Reuse Cached

Return cached result for repeated states

Code -

solution.c — C

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

#define MAX_STATES 100000

struct State {
    int reward;
    int mask;
    int result;
} memo[MAX_STATES];
int memoSize = 0;

int findMemo(int reward, int mask) {
    for (int i = 0; i < memoSize; i++) {
        if (memo[i].reward == reward && memo[i].mask == mask) {
            return memo[i].result;
        }
    }
    return -1;
}

void addMemo(int reward, int mask, int result) {
    if (memoSize < MAX_STATES) {
        memo[memoSize].reward = reward;
        memo[memoSize].mask = mask;
        memo[memoSize].result = result;
        memoSize++;
    }
}

int dp(int currentReward, int usedMask, int* rewardValues, int n) {
    int cached = findMemo(currentReward, usedMask);
    if (cached != -1) return cached;
    
    int maxReward = currentReward;
    for (int i = 0; i < n; i++) {
        if (!(usedMask & (1 << i)) && rewardValues[i] > currentReward) {
            int newMask = usedMask | (1 << i);
            int result = dp(currentReward + rewardValues[i], newMask, rewardValues, n);
            if (result > maxReward) maxReward = result;
        }
    }
    
    addMemo(currentReward, usedMask, maxReward);
    return maxReward;
}

int solution(int* rewardValues, int n) {
    memoSize = 0;
    return dp(0, 0, rewardValues, n);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    int rewardValues[1000];
    int n = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '[' && token[0] != ']') {
            rewardValues[n++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    printf("%d\n", solution(rewardValues, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × 2ⁿ × S)

n choices × 2^n possible used states × S possible sum values

✓ Linear Growth

Space Complexity

O(2ⁿ × S)

Memoization table stores results for each state combination

✓ Linear Space

17.0K Views

Medium Frequency

~25 min Avg. Time

680 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

Dynamic Programming with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler