[problem:1359D]↵
↵
[user:SXWisON,2023-12-20] [user:molingspance,2023-12-20]↵
↵
本题中可以采用动态规划中Kadane’s algorithm来实现↵
↵
### 原型↵
↵
Question: 已知序列a[i]；找出最优的索引l,r使得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]的值最大 + ... + a[r] is maximized.↵
↵
Kadane’s algorithm: ↵
↵
`localMax = Math.max(nums[i], localMax + nums[i]); `↵
↵
`max = Math.max(max, localMax); `↵
↵
###本题思路↵
↵
假定一个最值mx，将其从1~30遍历↵
↵
对于任意大于mx的数字，将其设为-INF，使优化过程只考虑xIdea↵
↵
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;↵
}↵
~~~~~↵
↵
↵
[user:SXWisON,2023-12-20] [user:molingspance,2023-12-20]↵
↵
↵
### 原型↵
↵
Question: 已知序列a[i]；找出最优的索引l,r使得
↵
### Prototype ↵
↵
Question: Given a sequence a[i], find the optimal indices l and r such that the sum of a[l]
↵
Kadane’s algorithm: ↵
↵
`localMax = Math.max(nums[i], localMax + nums[i])
↵
`max = Math.max(max, localMax)
↵
###
↵
假定一个最值mx，将其从1~30遍历↵
↵
对于任意大于mx的数字，将其设为-INF，使优化过程只考虑x
↵
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() {↵
//
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; //
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;↵
}↵
~~~~~↵
↵
