【LeetCode】删除并获得点数

链接: 删除并获得点数

题目描述

算法分析

编程代码

class Solution {
public:int deleteAndEarn(vector<int>& nums) {const int N = 10001;int arr[N] = {0};for(const auto& n : nums){arr[n]+=n;}vector<int> f(N);auto g = f;for(int i = 1;i<N;++i){f[i] = g[i-1]+arr[i];g[i] = max(g[i-1],f[i-1]);}return max(g[N-1],f[N-1]);}
};

空间优化

class Solution {
public:int deleteAndEarn(vector<int>& nums) {const int N = 10001;int arr[N] = {0};for(const auto& n : nums){arr[n]+=n;}int pre,back,ret;pre = back = ret = 0;for(int i = 1;i<N;++i){ret = back + arr[i];back = max(back,pre);pre = ret;}return max(ret,back);}
};