maximum-total-reward-using-operations-ii

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an integer array <code>rewardValues</code> of length <code>n</code>, representing the values of rewards.

Initially, your total reward <code>x</code> is 0, and all indices are unmarked. You are allowed to perform the following operation any number of times:

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

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

&nbsp;
Example 1:

<div class="example-block">
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.
</div>

Example 2:

<div class="example-block">
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.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= rewardValues.length &lt;= 5 * 104</code></li>
	<li><code>1 &lt;= rewardValues[i] &lt;= 5 * 104</code></li>
</ul>

maxTotalReward

Maximum Total Reward Using Operations II

Bit Manipulation

Array

Dynamic Programming

给你一个整数数组 <code>rewardValues</code>，长度为 <code>n</code>，代表奖励的值。

最初，你的总奖励 <code>x</code> 为 0，所有下标都是 未标记 的。你可以执行以下操作 任意次 ：

<ul>
	<li>从区间 <code>[0, n - 1]</code> 中选择一个 未标记 的下标 <code>i</code>。</li>
	<li>如果 <code>rewardValues[i]</code> 大于 你当前的总奖励 <code>x</code>，则将 <code>rewardValues[i]</code> 加到 <code>x</code> 上（即 <code>x = x + rewardValues[i]</code>），并 标记 下标 <code>i</code>。</li>
</ul>

以整数形式返回执行最优操作能够获得的 最大 总奖励。

&nbsp;

示例 1：

<div class="example-block">
输入：rewardValues = [1,1,3,3]

输出：4

解释：

依次标记下标 0 和 2，总奖励为 4，这是可获得的最大值。
</div>

示例 2：

<div class="example-block">
输入：rewardValues = [1,6,4,3,2]

输出：11

解释：

依次标记下标 0、2 和 1。总奖励为 11，这是可获得的最大值。
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= rewardValues.length &lt;= 5 * 104</code></li>
	<li><code>1 &lt;= rewardValues[i] &lt;= 5 * 104</code></li>
</ul>