2022-12-06:定义一个概念叫“变序最大和“ “变序最大和“是说一个数组中,每个值都可以减小或者不变, 在必须把整体变成严
2023-02-26 09:49:28 时间
2022-12-06:定义一个概念叫"变序最大和"
"变序最大和"是说一个数组中,每个值都可以减小或者不变,
在必须把整体变成严格升序的情况下,得到的最大累加和
比如,[1,100,7]变成[1,6,7]时,就有变序最大和为14
比如,[5,4,9]变成[3,4,9]时,就有变序最大和为16
比如,[1,4,2]变成[0,1,2]时,就有变序最大和为3
给定一个数组arr,其中所有的数字都是>=0的。
求arr所有子数组的变序最大和中,最大的那个并返回。
1 <= arr长度 <= 10^6,
0 <= arr[i] <= 10^6。
来自Amazon。
答案2022-12-06:
单调栈+dp。
时间复杂度:O(N)。
空间复杂度:O(N)。
代码用rust编写。代码如下:
use rand::Rng;
use std::iter::repeat;
fn main() {
let nn: i32 = 10;
let vv: i32 = 100;
let test_time: i32 = 50000;
println!("测试开始");
for _i in 0..test_time {
let n: i32 = rand::thread_rng().gen_range(0, nn) + 1;
let mut arr = random_array(n, vv);
arr = vec![1, 100, 7, 6];
let ans1 = max_sum1(&mut arr);
let ans2 = max_sum2(&mut arr);
if ans1 != ans2 {
println!("出错了!");
for num in &arr {
print!("{} ", num);
}
println!("");
println!("ans1 = {}", ans1);
println!("ans2 = {}", ans2);
break;
}
}
println!("测试结束");
}
// 时间复杂度O(N * V)的方法
// 为了验证
fn max_sum1(arr: &mut Vec<i32>) -> i64 {
let n = arr.len() as i32;
let mut max = 0;
for num in arr.iter() {
max = get_max(max, *num);
}
let mut ans = 0;
let mut dp: Vec<Vec<i64>> = repeat(repeat(0).take((max + 1) as usize).collect())
.take(n as usize)
.collect();
for i in 0..n {
for j in 0..=max {
dp[i as usize][j as usize] = -1;
}
}
for i in 0..n {
ans = get_max(ans, process1(arr, i, arr[i as usize], &mut dp));
}
return ans;
}
fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a > b {
a
} else {
b
}
}
fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a < b {
a
} else {
b
}
}
fn process1(arr: &mut Vec<i32>, i: i32, p: i32, dp: &mut Vec<Vec<i64>>) -> i64 {
if p <= 0 || i == -1 {
return 0;
}
if dp[i as usize][p as usize] != -1 {
return dp[i as usize][p as usize];
}
let cur = get_min(arr[i as usize], p);
let next = process1(arr, i - 1, cur - 1, dp);
let ans = cur as i64 + next;
dp[i as usize][p as usize] = ans;
return cur as i64 + next;
}
// 正式方法
// 时间复杂度O(N)
fn max_sum2(arr: &mut Vec<i32>) -> i64 {
let n = arr.len() as i32;
// 只放下标,只要有下标,arr可以拿到值
let mut stack: Vec<i32> = repeat(0).take(n as usize).collect();
let mut size = 0;
let mut dp: Vec<i64> = repeat(0).take(n as usize).collect();
let mut ans = 0;
for i in 0..n {
// i -> arr[i] 依次把收益!得到!
let mut cur_val = arr[i as usize];
let mut cur_idx = i;
// 20
// 17
while cur_val > 0 && size > 0 {
// 100
// 16
let left_idx = stack[(size - 1) as usize];
let left_val = arr[left_idx as usize];
if left_val >= cur_val {
size -= 1;
} else {
// leftVal < curVal
// 8 20
// 15 17
let idx_diff = cur_idx - left_idx;
let val_diff = cur_val - left_val;
// 12 2
// 8 19 20
// 15 16 17
if val_diff >= idx_diff {
dp[i as usize] += sum(cur_val, idx_diff) + dp[left_idx as usize];
cur_val = 0;
cur_idx = 0;
break;
} else {
// 18 20
// 13 14 15 16 17
// 17 18 19 20
// 16
dp[i as usize] += sum(cur_val, idx_diff);
// 16
// 13
cur_val -= idx_diff;
cur_idx = left_idx;
size -= 1;
}
}
}
if cur_val > 0 {
dp[i as usize] += sum(cur_val, cur_idx + 1);
}
stack[size as usize] = i;
size += 1;
ans = get_max(ans, dp[i as usize]);
}
return ans;
}
fn sum(max: i32, mut n: i32) -> i64 {
n = get_min(max, n);
((max as i64 * 2 - n as i64 + 1) * n as i64) / 2
}
// 为了验证
fn random_array(n: i32, v: i32) -> Vec<i32> {
let mut ans: Vec<i32> = vec![];
for _ in 0..n {
ans.push(rand::thread_rng().gen_range(0, v));
}
return ans;
}
执行结果如下:
***
[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_08_5_week/Code03_SubarrayMakeSrotedMaxSum.java)
相关文章
- Jgit的使用笔记
- 利用Github Action实现Tornadofx/JavaFx打包
- 叹息!GitHub Trending 即将成为历史!
- 微软软了?开源社区讨论炸锅,GitHub CEO 亲自来答
- GitHub Trending 列表频现重复项,前后端都没去重?
- Photoshop Elements 2021版本软件安装教程(mac+windows全版本都有)
- (ps全版本)Photoshop 2020的安装与破解教程(mac+windows全版本都有)
- (ps全版本)Photoshop cc2018的安装与破解教程(mac+windows全版本,包括2023
- 环境搭建:Oracle GoldenGate 大数据迁移到 Redshift/Flat file/Flume/Kafka测试流程
- 每个开发人员都要掌握的:最小 Linux 基础课
- 来撸羊毛了!Windows 环境下 Hexo 博客搭建,并部署到 GitHub Pages
- 超实用!手把手入门 MongoDB:这些坑点请一定远离
- 【GitHub日报】22-10-09 zustand、neovim、webtorrent、express 等4款App今日上新
- 【GitHub日报】22-10-10 brew、minio、vite、seaweedfs、dbeaver 等8款App今日上新
- 【GitHub日报】22-10-11 cobra、grafana、vue、ToolJet、redwood 等13款App今日上新
- Photoshop 2018 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2017 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2020 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2023 资源免费下载(mac+windows全版本都有,包括最新的2023)
- 最新版本Photoshop CC2018软件安装教程(mac+windows全版本都有,包括2023