3180. Maximum Total Reward Using Operations I Solution

Q: Is Maximum Total Reward Using Operations I easy or hard?

Maximum Total Reward Using Operations I is rated Medium difficulty. The challenge is recognizing that brute-force permutations are unnecessary and that the constraint value > currentSum can be modeled using dynamic programming states.

The 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.

Example 1:

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

Output: 4

Explanation:

During the operations, we can choose to mark the indices 0 and 2 in order, and the total reward will be 4, which is the maximum.

Example 2:

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

Output: 11

Explanation:

Mark the indices 0, 2, and 1 in order. The total reward will then be 11, which is the maximum.

Constraints:

1 <= rewardValues.length <= 2000
1 <= rewardValues[i] <= 2000

Approach overview

Problem Overview: You receive an array rewardValues. You may repeatedly pick an element only if its value is strictly greater than your current total reward. After picking it, the value is added to the total and the element becomes unusable. The goal is to maximize the final reward.

The constraint rewardValues[i] > currentSum creates an ordering dependency. Picking a value increases the sum, which may block other elements later. The core challenge is exploring valid reward sums without testing every permutation.

Approach 1: Greedy + Dynamic Programming with Sorting (O(n * M) time, O(M) space)

Sort the array first. Processing smaller rewards earlier gives you more opportunities to build valid intermediate sums. Maintain a boolean DP array (or bitset) where dp[s] means a total reward s is achievable. For each value v, iterate through all reachable sums s where s < v. If that condition holds, you can transition to s + v. Sorting ensures you always evaluate candidates in increasing order, which keeps the valid state space compact. The maximum reachable sum in the DP array becomes the answer. Time complexity is O(n * M), where M is the maximum reachable reward sum (bounded by roughly twice the largest value). Space complexity is O(M).

This approach blends array processing with dynamic programming. The greedy part (sorting) reduces invalid combinations, while DP tracks all feasible totals.

Approach 2: Iterative State Expansion Without Sorting (O(n * M) time, O(M) space)

Instead of sorting, maintain a set or boolean structure representing all reachable reward sums. For each value v, scan the current states and create new sums s + v only if s < v. Store the newly formed states separately and merge them into the global set afterward to avoid interfering with the same iteration. This effectively performs state expansion similar to subset-sum DP but with the additional constraint that the previous sum must be smaller than the chosen value.

This version keeps the algorithm purely iterative and avoids sorting, but it may process more intermediate states because values are not ordered. Time complexity remains O(n * M) with O(M) space, where M is the maximum tracked sum. It still relies heavily on dynamic programming state transitions.

Recommended for interviews: The sorted DP approach. Interviewers expect you to recognize the monotonic constraint (value > currentSum) and reduce permutations using sorting. Starting with a brute-force idea shows understanding of the rule, but the DP optimization demonstrates strong problem-solving and state modeling skills.

Approach 1: Greedy Approach Using Sorting

Sort the reward values in ascending order and iterate over them. At each step, if the current reward value is greater than the current total, add it to the total. This approach maximizes the reward by always adding the smallest possible value that increases the total, ensuring potential larger values can be added later.

Python

def maxTotalReward(rewardValues):
    rewardValues.sort()
    totalReward = 0
    for reward in rewardValues:
        if reward > totalReward:
            totalReward += reward
    return totalReward

rewardValues = [1, 6, 4, 3, 2]
print(maxTotalReward(rewardValues))

Java

import java.util.Arrays;

public class Main {
    public static int maxTotalReward(int[] rewardValues) {
        Arrays.sort(rewardValues);
        int totalReward = 0;
        for (int reward : rewardValues) {
            if (reward > totalReward) {
                totalReward += reward;
            }
        }
        return totalReward;
    }

    public static void main(String[] args) {
        int[] rewardValues = {1, 6, 4, 3, 2};
        System.out.println(maxTotalReward(rewardValues));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

int maxTotalReward(std::vector<int>& rewardValues) {
    std::sort(rewardValues.begin(), rewardValues.end());
    int totalReward = 0;
    for (int r : rewardValues) {
        if (r > totalReward) {
            totalReward += r;
        }
    }
    return totalReward;
}

int main() {
    std::vector<int> rewardValues = {1, 6, 4, 3, 2};
    std::cout << maxTotalReward(rewardValues);
    return 0;
}

JavaScript

function maxTotalReward(rewardValues) {
    rewardValues.sort((a, b) => a - b);
    let totalReward = 0;
    for (let reward of rewardValues) {
        if (reward > totalReward) {
            totalReward += reward;
        }
    }
    return totalReward;
}

const rewardValues = [1, 6, 4, 3, 2];
console.log(maxTotalReward(rewardValues));

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

int cmpfunc (const void * a, const void * b) {
   return (*(int*)a - *(int*)b);
}

int maxTotalReward(int* rewardValues, int size) {
    qsort(rewardValues, size, sizeof(int), cmpfunc);
    int totalReward = 0;
    for(int i = 0; i < size; i++) {
        if(rewardValues[i] > totalReward) {
            totalReward += rewardValues[i];
        }
    }
    return totalReward;
}

int main() {
    int rewardValues[] = {1, 6, 4, 3, 2};
    int size = sizeof(rewardValues) / sizeof(rewardValues[0]);
    printf("%d", maxTotalReward(rewardValues, size));
    return 0;
}

using System;

class Program {
    static int MaxTotalReward(int[] rewardValues) {
        Array.Sort(rewardValues);
        int totalReward = 0;
        foreach (var reward in rewardValues) {
            if (reward > totalReward) {
                totalReward += reward;
            }
        }
        return totalReward;
    }

    static void Main() {
        int[] rewardValues = { 1, 6, 4, 3, 2 };
        Console.WriteLine(MaxTotalReward(rewardValues));
    }
}

We sort the list of reward values and iterate over it, adding each item to the total if it is large enough to increase the total, hence following a greedy algorithmic approach.

Complexity

Time Complexity: O(n log n), because of sorting.
Space Complexity: O(1) assuming sorting can be done in place.

Try this approach in the editor

Approach 2: Iterative Approach Without Sorting

This approach iteratively chooses the largest value that can be added to the current total without sorting first. It utilizes a set or a boolean array to ensure indices are marked and not reused. This can potentially be less optimal than sorting but saves space used by sorting operations.

Python

def maxTotalReward(rewardValues):
    used = [False] * len(rewardValues)
    totalReward = 0
    for _ in range(len(rewardValues)):
        bestIndex = -1
        for i in range(len(rewardValues)):
            if not used[i] and rewardValues[i] > totalReward:
                if bestIndex == -1 or rewardValues[i] > rewardValues[bestIndex]:
                    bestIndex = i
        if bestIndex != -1:
            totalReward += rewardValues[bestIndex]
            used[bestIndex] = True
    return totalReward

rewardValues = [1, 6, 4, 3, 2]
print(maxTotalReward(rewardValues))

Java

public class Main {
    public static int maxTotalReward(int[] rewardValues) {
        boolean[] used = new boolean[rewardValues.length];
        int totalReward = 0;
        for (int it = 0; it < rewardValues.length; ++it) {
            int bestIndex = -1;
            for (int i = 0; i < rewardValues.length; ++i) {
                if (!used[i] && rewardValues[i] > totalReward) {
                    if (bestIndex == -1 || rewardValues[i] > rewardValues[bestIndex]) {
                        bestIndex = i;
                    }
                }
            }
            if (bestIndex != -1) {
                totalReward += rewardValues[bestIndex];
                used[bestIndex] = true;
            }
        }
        return totalReward;
    }

    public static void main(String[] args) {
        int[] rewardValues = {1, 6, 4, 3, 2};
        System.out.println(maxTotalReward(rewardValues));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

int maxTotalReward(std::vector<int>& rewardValues) {
    std::vector<bool> used(rewardValues.size(), false);
    int totalReward = 0;
    for (int it = 0; it < rewardValues.size(); ++it) {
        int bestIndex = -1;
        for (int i = 0; i < rewardValues.size(); ++i) {
            if (!used[i] && rewardValues[i] > totalReward) {
                if (bestIndex == -1 || rewardValues[i] > rewardValues[bestIndex]) {
                    bestIndex = i;
                }
            }
        }
        if (bestIndex != -1) {
            totalReward += rewardValues[bestIndex];
            used[bestIndex] = true;
        }
    }
    return totalReward;
}

int main() {
    std::vector<int> rewardValues = {1, 6, 4, 3, 2};
    std::cout << maxTotalReward(rewardValues);
    return 0;
}

JavaScript

function maxTotalReward(rewardValues) {
    let used = Array(rewardValues.length).fill(false);
    let totalReward = 0;
    for (let it = 0; it < rewardValues.length; ++it) {
        let bestIndex = -1;
        for (let i = 0; i < rewardValues.length; ++i) {
            if (!used[i] && rewardValues[i] > totalReward) {
                if (bestIndex === -1 || rewardValues[i] > rewardValues[bestIndex]) {
                    bestIndex = i;
                }
            }
        }
        if (bestIndex !== -1) {
            totalReward += rewardValues[bestIndex];
            used[bestIndex] = true;
        }
    }
    return totalReward;
}

const rewardValues = [1, 6, 4, 3, 2];
console.log(maxTotalReward(rewardValues));

#include <stdio.h>
#include <stdbool.h>
#define MAX_SIZE 2001

int maxTotalReward(int* rewardValues, int size) {
    bool used[MAX_SIZE] = {false};
    int totalReward = 0;
    for (int it = 0; it < size; ++it) {
        int bestIndex = -1;
        for (int i = 0; i < size; ++i) {
            if (!used[i] && rewardValues[i] > totalReward) {
                if (bestIndex == -1 || rewardValues[i] > rewardValues[bestIndex]) {
                    bestIndex = i;
                }
            }
        }
        if (bestIndex != -1) {
            totalReward += rewardValues[bestIndex];
            used[bestIndex] = true;
        }
    }
    return totalReward;
}

int main() {
    int rewardValues[] = {1, 6, 4, 3, 2};
    int size = sizeof(rewardValues) / sizeof(rewardValues[0]);
    printf("%d", maxTotalReward(rewardValues, size));
    return 0;
}

using System;

class Program {
    static int MaxTotalReward(int[] rewardValues) {
        bool[] used = new bool[rewardValues.Length];
        int totalReward = 0;
        for (int it = 0; it < rewardValues.Length; ++it) {
            int bestIndex = -1;
            for (int i = 0; i < rewardValues.Length; ++i) {
                if (!used[i] && rewardValues[i] > totalReward) {
                    if (bestIndex == -1 || rewardValues[i] > rewardValues[bestIndex]) {
                        bestIndex = i;
                    }
                }
            }
            if (bestIndex != -1) {
                totalReward += rewardValues[bestIndex];
                used[bestIndex] = true;
            }
        }
        return totalReward;
    }

    static void Main() {
        int[] rewardValues = { 1, 6, 4, 3, 2 };
        Console.WriteLine(MaxTotalReward(rewardValues));
    }
}

Python manages marked indices with a list of booleans, traversing through rewardValues, selecting and appending the best possible unmarked reward to the total in each iteration.

Complexity

Time Complexity: O(n^2) due to a comprehensive scan for the top addition.
Space Complexity: O(n) because of the boolean list tracking usage.

Try this approach in the editor

Approach 3: Sorting + Memoization + Binary Search

We can sort the rewardValues array and then use memoization to solve for the maximum total reward.

We define a function dfs(x), representing the maximum total reward that can be obtained when the current total reward is x. Thus, the answer is dfs(0).

The execution process of the function dfs(x) is as follows:

Perform a binary search in the rewardValues array for the index i of the first element greater than x;
Iterate over the elements in the rewardValues array starting from index i, and for each element v, calculate the maximum value of v + dfs(x + v).
Return the result.

To avoid repeated calculations, we use a memoization array f to record the results that have already been computed.

The time complexity is O(n times (log n + M)), and the space complexity is O(M). Where n is the length of the rewardValues array, and M is twice the maximum value in the rewardValues array.

TypeScript

function maxTotalReward(rewardValues: number[]): number {
    rewardValues.sort((a, b) => a - b);
    const search = (x: number): number => {
        let [l, r] = [0, rewardValues.length];
        while (l < r) {
            const mid = (l + r) >> 1;
            if (rewardValues[mid] > x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    };
    const f: number[] = Array(rewardValues.at(-1)! << 1).fill(-1);
    const dfs = (x: number): number => {
        if (f[x] !== -1) {
            return f[x];
        }
        let ans = 0;
        for (let i = search(x); i < rewardValues.length; ++i) {
            ans = Math.max(ans, rewardValues[i] + dfs(x + rewardValues[i]));
        }
        return (f[x] = ans);
    };
    return dfs(0);
}

func maxTotalReward(rewardValues []int) int {
	sort.Ints(rewardValues)
	n := len(rewardValues)
	f := make([]int, rewardValues[n-1]<<1)
	for i := range f {
		f[i] = -1
	}
	var dfs func(int) int
	dfs = func(x int) int {
		if f[x] != -1 {
			return f[x]
		}
		i := sort.SearchInts(rewardValues, x+1)
		f[x] = 0
		for _, v := range rewardValues[i:] {
			f[x] = max(f[x], v+dfs(x+v))
		}
		return f[x]
	}
	return dfs(0)
}

Try this approach in the editor

Approach 4: Dynamic Programming

We define f[i][j] as whether it is possible to obtain a total reward of j using the first i reward values. Initially, f[0][0] = True, and all other values are False.

We consider the i-th reward value v. If we do not choose it, then f[i][j] = f[i - 1][j]. If we choose it, then f[i][j] = f[i - 1][j - v], where 0 leq j - v < v. Thus, the state transition equation is:

$f[i][j] = f[i - 1][j] \vee f[i - 1][j - v]

The final answer is max{j \mid f[n][j] = True}.

Since f[i][j] only depends on f[i - 1][j] and f[i - 1][j - v], we can optimize away the first dimension and use only a one-dimensional array for state transitions.

The time complexity is O(n times M), and the space complexity is O(M). Where n is the length of the rewardValues array, and M$ is twice the maximum value in the rewardValues array.

TypeScript

function maxTotalReward(rewardValues: number[]): number {
    const nums = Array.from(new Set(rewardValues)).sort((a, b) => a - b);
    const n = nums.length;
    const m = nums[n - 1] << 1;
    const f: boolean[] = Array(m).fill(false);
    f[0] = true;
    for (const v of nums) {
        for (let j = 1; j < m; ++j) {
            if (0 <= j - v && j - v < v) {
                f[j] = f[j] || f[j - v];
            }
        }
    }
    let ans = m - 1;
    while (!f[ans]) {
        --ans;
    }
    return ans;
}

func maxTotalReward(rewardValues []int) int {
	slices.Sort(rewardValues)
	nums := slices.Compact(rewardValues)
	n := len(nums)
	m := nums[n-1] << 1
	f := make([]bool, m)
	f[0] = true
	for _, v := range nums {
		for j := 1; j < m; j++ {
			if 0 <= j-v && j-v < v {
				f[j] = f[j] || f[j-v]
			}
		}
	}
	ans := m - 1
	for !f[ans] {
		ans--
	}
	return ans
}

Try this approach in the editor

Approach 5: Dynamic Programming + Bit Manipulation

We can optimize Solution 2 by defining a binary number f to save the current state, where the i-th bit of f being 1 indicates that a total reward of i is reachable.

Observing the state transition equation from Solution 2, f[j] = f[j] \vee f[j - v], this is equivalent to taking the lower v bits of f, shifting them left by v bits, and then performing an OR operation with the original f.

Thus, the answer is the position of the highest bit in f.

The time complexity is O(n times M / w), and the space complexity is O(n + M / w). Where n is the length of the rewardValues array, M is twice the maximum value in the rewardValues array, and the integer w = 32 or 64.

TypeScript

function maxTotalReward(rewardValues: number[]): number {
    rewardValues.sort((a, b) => a - b);
    rewardValues = [...new Set(rewardValues)];
    let f = 1n;
    for (const x of rewardValues) {
        const mask = (1n << BigInt(x)) - 1n;
        f = f | ((f & mask) << BigInt(x));
    }
    return f.toString(2).length - 1;
}

func maxTotalReward(rewardValues []int) int {
	slices.Sort(rewardValues)
	rewardValues = slices.Compact(rewardValues)
	one := big.NewInt(1)
	f := big.NewInt(1)
	p := new(big.Int)
	for _, v := range rewardValues {
		mask := p.Sub(p.Lsh(one, uint(v)), one)
		f.Or(f, p.Lsh(p.And(f, mask), uint(v)))
	}
	return f.BitLen() - 1
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Approach Using Sorting	Time Complexity: O(n log n), because of sorting. Space Complexity: O(1) assuming sorting can be done in place.
Iterative Approach Without Sorting	Time Complexity: O(n^2) due to a comprehensive scan for the top addition. Space Complexity: O(n) because of the boolean list tracking usage.
Sorting + Memoization + Binary Search	–
Dynamic Programming	–
Dynamic Programming + Bit Manipulation	–

Complexity analysis

Approach	Time	Space	When to Use
Greedy + DP with Sorting	O(n * M)	O(M)	Best general solution. Sorting reduces invalid states and keeps transitions efficient.
Iterative State Expansion (No Sorting)	O(n * M)	O(M)	Useful when preserving original order or when sorting is restricted.

Frequently asked questions

Is Maximum Total Reward Using Operations I easy or hard?

Maximum Total Reward Using Operations I is rated Medium difficulty. The challenge is recognizing that brute-force permutations are unnecessary and that the constraint value > currentSum can be modeled using dynamic programming states.

Maximum Total Reward Using Operations I Python/Java solution

Python and Java implementations typically use a boolean DP array or bitset. After sorting the rewards, iterate through values and update reachable sums where the previous sum is smaller than the current value. This approach keeps transitions efficient and avoids exploring invalid states.

How to solve Maximum Total Reward Using Operations I in O(n)?

A strict O(n) solution is generally not feasible because the algorithm must track multiple reachable reward sums. The closest optimal strategy uses dynamic programming with a bounded sum space, giving O(n * M) time where M is limited by the maximum reward value.

What is the best approach for Maximum Total Reward Using Operations I?

The most efficient approach sorts the reward values and uses dynamic programming to track reachable reward sums. For each value v, transitions are allowed only from sums smaller than v. This reduces invalid states and runs in O(n * M) time with O(M) space, where M is the maximum achievable reward sum.

Is Maximum Total Reward Using Operations I asked at Google/Amazon/Meta?

Problems combining greedy ordering with dynamic programming frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of constrained subset-sum or reward maximization are common in coding interviews and competitive programming platforms.

What data structure is used in Maximum Total Reward Using Operations I?

The core structure is a dynamic programming array or bitset that tracks reachable reward sums. Some implementations also use sets to store intermediate sums. The algorithm primarily relies on array processing and dynamic programming transitions.

What is the time complexity of Maximum Total Reward Using Operations I?

The optimized solution runs in O(n * M) time, where n is the number of reward values and M is the maximum reachable sum tracked in the DP structure. Space complexity is O(M). Sorting the array adds an additional O(n log n) step but does not dominate overall complexity.

Maximum Total Reward Using Operations I solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach Using Sorting

Approach 2: Iterative Approach Without Sorting

Approach 3: Sorting + Memoization + Binary Search

Approach 4: Dynamic Programming

Approach 5: Dynamic Programming + Bit Manipulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Maximum Total Reward Using Operations I solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach Using Sorting

Approach 2: Iterative Approach Without Sorting

Approach 3: Sorting + Memoization + Binary Search

Approach 4: Dynamic Programming

Approach 5: Dynamic Programming + Bit Manipulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems