Problem Notes
Difference between en2 and en3, changed 25 character(s)
[problem:1359D]↵
↵
[user:SXWisON],2023-12-20] [user:molingspance,2023-12-20]↵
↵
本题中可以采用动态规划中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;↵
}↵
~~~~~↵
↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English SXWisON 2023-12-21 07:12:58 533 Tiny change: '\n#include<algorithm' -> '\n#include <algorithm'
en3 English SXWisON 2023-12-20 19:31:17 25 Tiny change: 'r:SXWisON][user:moli' -> 'r:SXWisON] [user:moli'
en2 English SXWisON 2023-12-20 19:30:20 54 Tiny change: '本题中可以采用动态规' -> '[problem:1359D]\n[user:SXWisON][user:molingspance]\n\n本题中可以采用动态规'
en1 English SXWisON 2023-12-20 19:24:31 1014 Initial revision (published)