题目描述：
给你一个下标从 0 开始的整数数组 nums 。
nums 一个长度为 k 的 子序列 指的是选出 k 个 下标 i0 < i1 < ... < ik-1 ，如果这个子序列满足以下条件，我们说它是 平衡的 ：
- 对于范围
[1, k - 1] 内的所有 j ， $nums[i_j] - nums[i_{j - 1}] \ge i_j - i_{j - 1}$ 都成立。
nums 长度为 1 的 子序列 是平衡的。
请你返回一个整数，表示 nums 平衡 子序列里面的 最大元素和 。
一个数组的 子序列 指的是从原数组中删除一些元素（也可能一个元素也不删除）后，剩余元素保持相对顺序得到的 非空 新数组。
数据范围：
$1\le nums.len \le 10^5; -10^9 \le nums[i] \le 10^9$
题解：
首先需要对这个公式进行转化， $nums[i_j] - i_j \ge nums[i_{j - 1}] - i_{j - 1}$ 。然后就会发现需要找出来上升子序列，找上升子序列最大值。可以考虑使用动态规划的做法。
初始状态： $dp[i] = nums[i]$
但是 $O(n^2)$ 的复杂度肯定过不了，需要考虑优化，可以考虑使用线段树或者树状数组优化，套路非常固定，就是把原来数组中的元素映射到区间上，快速查询区间 $[-\infty, nums[i] - i]$ 的最大值。
该类的题目都需要最终转化为求某个区间的最值，这个区间与数值有关，需要使用离散化操作得到以 $1$ 开头的区间。离散化有两种操作，一种是使用 unique，另一种是使用 unordered_map。
使用 unique 离散化
1
2
3
4
| sort(b.begin(), b.end());
int size = unique(b.begin(), b.end()) - b.begin();
for(int i = 0; i < size; ++i)
b[i] = lower_bound(b + i, b + size, b[i]) - b;
|
使用 unordered_map 离散化
1
2
3
4
5
6
| int size = 1;
unordered_map<int, int> mp;
for(auto& x: nums)
{
if(!mp.count(x)) mp[x] = size++;
}
|
注意，因为使用线段树或者树状数组，所以需要保证最小的数映射到 $1$ 。
线段树做法：
在这里就是 $-\infty$ 映射到 $1$ ，然后构造一棵单点修改，区间最值的线段树，每次查询 $[1, nums[i] - i]$ 的区间最大值 pre，然后使用 pre 更新答案，最后修改 $nums[i] - i$ 这一点的值，修改为 $nums[i] + pre$ 。
树状数组做法：
树状数组用来维护区间 $[1,x]$ 区间信息，如果维护 $[x,y]$ 可以通过前缀和差分得到，但是最值的话不方便。
树状数组，每个节点 $u$ 的父节点为 $lowbit(u)$ 。其中 lowbit(x) = x & -x。
查询时，查 $[1,x]$ ，则：查询时从区间右端点出发，每次左移 $lowbit(x)$ 。
1
2
3
4
5
6
7
8
9
10
| long long query(int r)
{
long long maxx = 0;
while(x >= 1)
{
maxx = max(tree[x], maxx);
x -= lowbit(x);
}
return x;
}
|
更新时，更新 $x$ ，则：直接更新辅助数组 $c[x]$ ，然后从 $x$ 每次右移 $lowbit(x)$ ，更新父亲。
1
2
3
4
5
6
7
8
9
10
11
12
| void update(int pos, long long k)
{
if (k < tree[pos])
return;
tree[pos] = k;
pos += lowbit(pos);
while (pos <= n)
{
tree[pos] = max(tree[pos], k);
pos += lowbit(pos);
}
}
|
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
| const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
struct SegTree
{
struct TreeNode
{
long long val;
long long tag;
int l, r;
};
vector<TreeNode> tree;
SegTree(int n) : tree(n << 2) {}
void build(int cur, int l, int r)
{
tree[cur].l = l, tree[cur].r = r;
tree[cur].tag = 0;
if (l == r)
{
tree[cur].val = 0;
return;
}
int mid = (l + r) >> 1;
build(cur << 1, l, mid);
build(cur << 1 | 1, mid + 1, r);
tree[cur].val = max(tree[cur << 1].val, tree[cur << 1 | 1].val);
}
void update(int cur, int pos, long long k)
{
if (tree[cur].l == pos && tree[cur].r == pos)
{
tree[cur].val = max(k, tree[cur].val);
return;
}
int mid = (tree[cur].l + tree[cur].r) >> 1;
if (pos <= mid)
update(cur << 1, pos, k);
if (pos >= mid + 1)
update(cur << 1 | 1, pos, k);
tree[cur].val = max(tree[cur << 1].val, tree[cur << 1 | 1].val);
}
long long query(int cur, int l, int r)
{
if (l <= tree[cur].l && tree[cur].r <= r)
return tree[cur].val;
int mid = (tree[cur].l + tree[cur].r) >> 1;
long long maxx = 0;
if (l <= mid)
maxx = max(maxx, query(cur << 1, l, r));
if (mid + 1 <= r)
maxx = max(maxx, query(cur << 1 | 1, l, r));
return maxx;
}
};
auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
long long maxBalancedSubsequenceSum(vector<int> &nums)
{
int n = nums.size();
for (int i = 0; i < n; ++i)
{
nums[i] -= i;
}
auto b = nums;
sort(b.begin(), b.end());
int size = 1;
unordered_map<int, int> mp;
mp[-INF_LL] = size++;
for (auto &x : b)
{
if (!mp.count(x))
mp[x] = size++;
}
SegTree segTree(size);
segTree.build(1, 1, size);
long long ans = -INF_LL;
for (int i = 0; i < n; ++i)
{
int x = mp[nums[i]];
long long pre = segTree.query(1, 1, x);
ans = max(ans, pre + nums[i] + i);
segTree.update(1, x, pre + nums[i] + i);
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
| const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
struct BIT
{
vector<long long> tree;
int n;
BIT(int _n) : tree(_n + 1), n(_n) {}
int lowbit(int x)
{
return x & -x;
}
void build(int cur, int l, int r)
{
for (int i = 1; i <= n; ++i)
{
tree[i] = 0;
int j = i + lowbit(i);
if (j <= n)
tree[j] = max(tree[j], tree[i]);
}
}
void update(int pos, long long k)
{
if (k < tree[pos])
return;
tree[pos] = k;
pos += lowbit(pos);
while (pos <= n)
{
tree[pos] = max(tree[pos], k);
pos += lowbit(pos);
}
}
long long query(int r)
{
long long maxx = 0;
while (r >= 1)
{
maxx = max(maxx, tree[r]);
r -= lowbit(r);
}
return maxx;
}
};
auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
long long maxBalancedSubsequenceSum(vector<int> &nums)
{
int n = nums.size();
for (int i = 0; i < n; ++i)
{
nums[i] -= i;
}
auto b = nums;
sort(b.begin(), b.end());
int size = 1;
unordered_map<int, int> mp;
mp[-INF_LL] = size++;
for (auto &x : b)
{
if (!mp.count(x))
mp[x] = size++;
}
BIT bit(size);
bit.build(1, 1, size);
long long ans = -INF_LL;
for (int i = 0; i < n; ++i)
{
int x = mp[nums[i]];
long long pre = bit.query(x);
ans = max(ans, pre + nums[i] + i);
bit.update(x, pre + nums[i] + i);
}
return ans;
}
};
|