1359D - Yet Another Yet Another Task [user:SXWisON][user:molingspance]

本题中可以采用动态规划中Kadane’s algorithm来实现

原型

Question: 已知序列a[i]；找出最优的索引l,r使得a[l]+...+a[r]的值最大

Kadane’s algorithm:

localMax = Math.max(nums[i], localMax + nums[i]);

max = Math.max(max, localMax);

本题思路

假定一个最值mx，将其从1~30遍历

对于任意大于mx的数字，将其设为-INF，使优化过程只考虑x<=mx的值

localMax = Math.max(nums[i], localMax + nums[i]);

max = Math.max(max, localMax-mx);

Code

#include <iostream>
#include<algorithm>

int a[100010];

typedef long long int LL;
constexpr int INF = 10e9;

int main() {
  // 读取数据
  int n;
  std::cin >> n;
  for (int i = 0;i < n;i++) {
    std::cin >> a[i];
  }
  // 迭代
  LL Gmax = 0;
  for (int mx = 1; mx <= 30; mx++) {
    LL Lmax = 0;  // 局部最大值（指单个mx
    LL cur = 0;    // 当前最大值
    for (int i = 0; i < n; i++) {
      LL val = (a[i] > mx) ? -INF : a[i];
      cur = std::max(val, cur + val);
      Lmax = std::max(cur, Lmax);
    }
    Gmax = std::max(Lmax - mx, Gmax);
  }
  std::cout << Gmax;
  return 0;
}