Liupeng
Jun 7, 2020
带限制的子序列和
Title
MyCode
int Paly1425::constrainedSubsetSum(std::vector<int> &nums, int k) {
int f[100005], ans = -99999;//f即为nums[i]结尾的子序列和的最大值
std::deque<std::pair<int,int> > s;
int n = nums.size();
for(int i = 0; i < n; i++){
f[i] = nums[i];
f[i] = max(f[i], f[i] + s.front().first);
ans = max(ans, f[i]);//记录答案
if(s.empty()) s.push_back(std::make_pair(f[i],i));
else{
//保证队列是单调递减的
while(!s.empty() && f[i] >= s.back().first) s.pop_back();
s.push_back(std::make_pair(f[i],i));
}
//如果队首已经超出了[i-k,i]的范围就把队首弹出
while(!s.empty() && s.front().second <= i - k) s.pop_front();
}
return ans;
}