2025-01-16：执行操作可获得的最大总奖励Ⅱ。用go语言，给定一个整数数组 rewardValues，长度为 n，表示奖励的数值。

最开始，你的总奖励 x 为 0，数组中的所有下标都标记为“未标记”。你可以执行以下操作任意次：

1.从数组中选择一个“未标记”的下标 i，范围为 [0, n - 1]。

2.如果 rewardValues[i] 大于当前的总奖励 x，则将 rewardValues[i] 加入到 x 中（即 x = x + rewardValues[i]），并将下标 i 标记为“已标记”。

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

1 <= rewardValues.length <= 5 * 10000。

1 <= rewardValues[i] <= 5 * 10000。

输入：rewardValues = [1,6,4,3,2]。

输出：11。

解释：

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

答案2025-01-16：

chatgpt

题目来自leetcode3181。

大体步骤如下：

1.首先给 rewardValues 排序，使得数组中的奖励值从小到大排列。

2.判断是否有连续两个奖励值相邻且差值为1，如果存在这样的情况，那么选中这两个奖励值将得到最大奖励。

3.如果不存在连续两个奖励值相邻且差值为1的情况，那么进行动态规划计算：

• 利用两个 big.Int 类型的变量 f0 和 f1，f0 代表之前的总奖励情况，f1 则表示考虑当前奖励值后的总奖励情况。

• 遍历 rewardValues 数组，对每个奖励值进行处理。

• 创建一个 mask 对应当前奖励值，设置相应位为 1，其它位为 0。

• 利用 f1 按位与 mask 的结果左移奖励值位数，并更新 f1。

• 利用或操作将 f1 合并到 f0。

4.返回 f0 的二进制位长度减去1，即为最大总奖励。

总的时间复杂度：

• 排序数组的时间复杂度为 O(nlogn)，n 为数组长度。

• 动态规划部分时间复杂度为O(n)，n 为数组长度。

• 因此总的时间复杂度为 O(nlogn)。

总的额外空间复杂度：

• 除了排序需要 O(logn) 的额外空间外，动态规划部分只使用了常数级别的额外空间。

• 所以总的额外空间复杂度为 O(logn)。

Go完整代码如下：

package main

import (
	"fmt"
	"math/big"
	"sort"
)

func maxTotalReward(rewardValues []int) int {
	n := len(rewardValues)
	sort.Ints(rewardValues)
	if n >= 2 && rewardValues[n-2] == rewardValues[n-1]-1 {
		return 2*rewardValues[n-1] - 1
	}
	f0, f1 := big.NewInt(1), big.NewInt(0)
	for _, x := range rewardValues {
		mask, one := big.NewInt(0), big.NewInt(1)
		mask.Sub(mask.Lsh(one, uint(x)), one)
		f1.Lsh(f1.And(f0, mask), uint(x))
		f0.Or(f0, f1)
	}
	return f0.BitLen() - 1
}

func main() {
	rewardValues := []int{1, 6, 4, 3, 2}
	result := maxTotalReward(rewardValues)
	fmt.Println(result)
}

Rust完整代码如下：

fn max_total_reward(reward_values: Vec<i32>) -> i32 {
    let mut reward_values = reward_values.clone();
    reward_values.sort();
    let n = reward_values.len();

    // 如果倒数第二个和倒数第一个元素满足条件
    if n >= 2 && reward_values[n - 2] == reward_values[n - 1] - 1 {
        return 2 * reward_values[n - 1] - 1;
    }

    let mut f0 = 1_u64;
    let mut f1 = 0_u64;

    for &x in &reward_values {
        let mut mask = 0_u64;
        let one = 1_u64;
        mask = (one << x) - one; // 构造遮罩
        f1 = (f0 & mask) << x; // 更新 f1
        f0 |= f1; // 更新 f0
    }

    64 - f0.leading_zeros() as i32 - 1
}

fn main() {
    let reward_values = vec![1, 6, 4, 3, 2];
    let result = max_total_reward(reward_values);
    println!("{}", result);
}

C完整代码如下：

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

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

int maxTotalReward(int *rewardValues, int n) {
    qsort(rewardValues, n, sizeof(int), compare);

    if (n >= 2 && rewardValues[n - 2] == rewardValues[n - 1] - 1) {
        return 2 * rewardValues[n - 1] - 1;
    }

    unsigned long long f0 = 1, f1 = 0;
    for (int i = 0; i < n; i++) {
        unsigned long long mask = (1ULL << rewardValues[i]) - 1;
        f1 = (f0 & mask) << rewardValues[i];
        f0 |= f1;
    }

    // 计算 f0 的二进制位数
    int bit_length = 0;
    while (f0 > 0) {
        bit_length++;
        f0 >>= 1; // 右移一位
    }

    return bit_length - 1; // 返回有效位数减去 1
}

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

C++完整代码如下：

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

int maxTotalReward(std::vector<int>& rewardValues) {
    int n = rewardValues.size();
    std::sort(rewardValues.begin(), rewardValues.end());

    // 特殊情况判断
    if (n >= 2 && rewardValues[n - 2] == rewardValues[n - 1] - 1) {
        return 2 * rewardValues[n - 1] - 1;
    }

    // 使用一个长整型来模拟大整数
    unsigned long long f0 = 1, f1 = 0;
    for (int x : rewardValues) {
        unsigned long long mask = (1ULL << x) - 1;
        f1 = (f0 & mask) << x;
        f0 |= f1;
    }

    // 使用 bitset 来计算 f0 的有效位长度
    return static_cast<int>(std::bitset<64>(f0).count()) - 1;
}

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

Python完整代码如下：

# -*-coding:utf-8-*-

def max_total_reward(reward_values):
    # 排序
    reward_values.sort()
    n = len(reward_values)
    
    # 特殊情况处理
    if n >= 2 and reward_values[-2] == reward_values[-1] - 1:
        return 2 * reward_values[-1] - 1

    # 初始化 f0 和 f1
    f0 = 1
    for x in reward_values:
        mask = (1 << x) - 1  # 创建掩码
        f1 = (f0 & mask) << x  # 计算新的 f1
        f0 |= f1  # 更新 f0

    # 计算 f0 的二进制位长度
    return f0.bit_length() - 1

if __name__ == "__main__":
    reward_values = [1, 6, 4, 3, 2]
    result = max_total_reward(reward_values)
    print(result)

JavaScript完整代码如下：

function maxTotalReward(rewardValues) {
    const n = rewardValues.length;
    rewardValues.sort((a, b) => a - b);

    // 特殊情况处理
    if (n >= 2 && rewardValues[n - 2] === rewardValues[n - 1] - 1) {
        return 2 * rewardValues[n - 1] - 1;
    }

    let f0 = BigInt(1);
    let f1 = BigInt(0);
    
    for (const x of rewardValues) {
        const mask = (BigInt(1) << BigInt(x)) - BigInt(1);
        f1 = (f0 & mask) << BigInt(x);
        f0 |= f1;
    }

    // 计算 f0 的二进制位长度
    return f0.toString(2).length - 1;
}

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

Solidity完整代码如下：

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

contract RewardCalculator {
    function maxTotalReward(uint256[] memory rewardValues) public pure returns (uint256) {
        uint256 n = rewardValues.length;

        // 排序
        for (uint256 i = 0; i < n - 1; i++) {
            for (uint256 j = i + 1; j < n; j++) {
                if (rewardValues[j] < rewardValues[i]) {
                    uint256 temp = rewardValues[i];
                    rewardValues[i] = rewardValues[j];
                    rewardValues[j] = temp;
                }
            }
        }

        // 特殊情况处理
        if (n >= 2 && rewardValues[n - 2] == rewardValues[n - 1] - 1) {
            return 2 * rewardValues[n - 1] - 1;
        }

        uint256 f0 = 1; // 初始值
        uint256 f1;
        
        // 位运算
        for (uint256 i = 0; i < n; i++) {
            uint256 mask = (1 << rewardValues[i]) - 1; // 计算掩码
            f1 = (f0 & mask) << rewardValues[i];       // 新值
            f0 |= f1;                                  // 更新 f0
        }

        // 计算有效位长度
        return bitLength(f0) - 1;
    }

    function bitLength(uint256 value) internal pure returns (uint256) {
        uint256 length = 0;
        while (value > 0) {
            value >>= 1; // 将值右移，丢弃最低位
            length++;
        }
        return length;
    }
}