题目链接：https://leetcode-cn.com/problems/constrained-subsequence-sum/
思路：动态规划 dp[i] = Max(nums[i], nums[i] + dp[i + j]) 其中0 < j <= k，但是直接遍历dp[i + j]会超时，所以要维护一个能快速查找dp[i + j]中最大值的结构，可以使用单调栈，也可以用平衡二叉树，由于Ｃ＃中没有双向队列，干脆就直接拷个Splay树过来。
public class Solution {
class SplayTree {
public SplayNode Root;
public class SplayNode {
//结点为根的子树中总共有多少个结点
public int Size;
//当前结点有多少个Value
public int Count;
//当前结点的值
public long Value;
//父结点
public SplayNode Pre;
//左右子结点
public SplayNode[] Childs = new SplayNode[2];
public SplayNode(long _value, SplayNode _pre, SplayNode left = null, SplayNode right = null) {
Size = 1;
Count = 1;
Value = _value;
Pre = _pre;
Childs[0] = left;
Childs[1] = right;
}
}
public SplayTree() {
//创建两个边界结点
Root = new SplayNode(long.MinValue, null);
Root.Childs[1] = new SplayNode(long.MaxValue, Root);
PushUp(Root);
}
/// <summary>
/// 返回子节点方向
/// </summary>
/// <param name="rw"></param>
/// <returns>rw是父结点的左儿子返回0，右儿子返回1</returns>
public int F(SplayNode rw) {
if (rw.Pre.Childs[0] == rw) {
return 0;
}
return 1;
}
/// <summary>
/// 向上更新状态
/// </summary>
public void PushUp(SplayNode rt) {
rt.Size = rt.Count;
for (int i = 0; i < 2; i++) {
if (null != rt.Childs[i]) {
rt.Childs[i].Pre = rt;
rt.Size += rt.Childs[i].Size;
}
}
}
//将rw旋转到父结点的位置
public void Rotate(SplayNode rw) {
int chd = F(rw);
SplayNode preNode = rw.Pre;
rw.Pre = preNode.Pre;
if (null != preNode.Pre) {
preNode.Pre.Childs[F(preNode)] = rw;
}
preNode.Childs[chd] = rw.Childs[1 - chd];
rw.Childs[1 - chd] = preNode;
PushUp(preNode);
PushUp(rw);
}
/// <summary>
/// 调整SplayTree, 将rw调整到rt的子结点
/// </summary>
/// <returns></returns>
public SplayNode Splay(SplayNode rt, SplayNode rw) {
while (rw.Pre != rt) {
SplayNode preNode = rw.Pre;
if (rt == preNode.Pre || F(rw) != F(preNode)) {
Rotate(rw);
} else {
Rotate(preNode);
Rotate(rw);
}
}
if (null != rt) {
PushUp(rt);
} else {
Root = rw;
}
return rw;
}
/// <summary>
/// 插入结点
/// </summary>
/// <param name="value"></param>
/// <returns></returns>
public SplayNode Insert(long value) {
SplayNode curNode = Root;
SplayNode newNode = new SplayNode(value, null);
while (true) {
curNode.Size++;
int nextChd = 0;
if (value == curNode.Value) {
newNode = curNode;
newNode.Count++;
break;
} else if (value < curNode.Value) {
nextChd = 0;
} else {
nextChd = 1;
}
if (null == curNode.Childs[nextChd]) {
newNode.Pre = curNode;
curNode.Childs[nextChd] = newNode;
break;
}
curNode = curNode.Childs[nextChd];
}
return newNode;
}
/// <summary>
/// 删除结点
/// </summary>
/// <param name="value"></param>
/// <returns></returns>
public bool Delete(long value) {
SplayNode node = FindRange(value, value);
if (null == node) {
return false;
}
node.Count--;
node.Size--;
if (node.Count <= 0) {
//删除结点
node.Pre.Childs[F(node)] = null;
}
//减小size
SplayNode curNode = node;
while (null != curNode.Pre) {
curNode = curNode.Pre;
PushUp(curNode);
}
return true;
}
/// <summary>
/// 返回小于value的最大的Node
/// </summary>
/// <param name="value"></param>
/// <returns></returns>
public SplayNode FindNode1(long value) {
SplayNode retNode = null;
SplayNode curNode = Root;
while (null != curNode) {
if (value <= curNode.Value) {
curNode = curNode.Childs[0];
} else {
if (null != curNode && (null == retNode || retNode.Value < curNode.Value)) {
retNode = curNode;
}
curNode = curNode.Childs[1];
}
}
return retNode;
}
/// <summary>
/// 返回大于value的最小的Node
/// </summary>
/// <param name="value"></param>
/// <returns></returns>
public SplayNode FindNode2(long value) {
SplayNode retNode = null;
SplayNode curNode = Root;
while (null != curNode) {
if (value < curNode.Value) {
if (null != curNode && (null == retNode || curNode.Value < retNode.Value)) {
retNode = curNode;
}
curNode = curNode.Childs[0];
} else {
curNode = curNode.Childs[1];
}
}
return retNode;
}
/// <summary>
/// 将区间内所有结点放到一个子树上，并返回子树根结点
/// </summary>
/// <param name="min"></param>
/// <param name="max"></param>
/// <returns></returns>
public SplayNode FindRange(long min, long max) {
SplayNode minNode = FindNode1(min);
SplayNode maxNode = FindNode2(max);
//minNode旋转到Root
Splay(null, minNode);
//maxNode旋转为Root右子结点
Splay(minNode, maxNode);
return maxNode.Childs[0];
}
}
int[] DP = new int[100005];
public int ConstrainedSubsetSum(int[] nums, int k) {
SplayTree tree = new SplayTree();
for (int i = nums.Length - 1; 0 <= i; i--) {
DP[i] = nums[i];
if (i + k + 1 < nums.Length) {
//删除旧结点
tree.Delete(DP[i + k + 1]);
}
var node = tree.FindNode1(long.MaxValue);
DP[i] = (int)Math.Max(DP[i], node.Value + nums[i]);
//插入新结点
tree.Splay(null, tree.Insert(DP[i]));
}
int result = DP[0];
for (int i = 1; i < nums.Length; i++) {
result = Math.Max(result, DP[i]);
}
return result;
}
}
文章评论