1359D - Yet Another Yet Another Task

SXWisON molingspance

In this problem, we can use Kadane’s algorithm in dynamic programming to solve it.

Prototype

Question: Given a sequence a[i], find the optimal indices l and r such that the sum of a[l] + ... + a[r] is maximized.

Kadane’s algorithm:

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

max = Math.max(max, localMax)

Idea

Suppose we have a maximum value mx and we iterate through the range 1 to 30.

For any number greater than mx, we set it to negative infinity so that the optimization process only considers values where 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() {
  // load data
  int n;
  std::cin >> n;
  for (int i = 0;i < n;i++) {
    std::cin >> a[i];
  }
  // iteration
  LL Gmax = 0;
  for (int mx = 1; mx <= 30; mx++) {
    LL Lmax = 0;  // Local max for signle mx
    LL cur = 0;    // Current max
    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;
}