2022-11-18：给定一个数组 arr，表示连续 n 天的股价，数组下标表示第几天指标 X：任意两天的股价之和 - 此两天间隔的天数比如第 3 天，价格是 10 第 9 天，价格是 30 那么第 3 天和第 9 天的指

2022-11-18
北京
本文字数：473 字
阅读完需：约 2 分钟

2022-11-18：给定一个数组 arr，表示连续 n 天的股价，数组下标表示第几天指标 X：任意两天的股价之和 - 此两天间隔的天数比如第 3 天，价格是 10 第 9 天，价格是 30 那么第 3 天和第 9 天的指标 X = 10 + 30 - (9 - 3) = 34。返回 arr 中最大的指标 X。时间复杂度 O(N)。来自神策。

答案 2022-11-18：

一次遍历即可。时间复杂度：O(N)。额外空间复杂度：O(1)。

代码用 rust 编写。代码如下：

fn main() {    let mut nums = vec![2, 3, 1, 4, 0];    let ans = max_x(&mut nums);    println!("ans = {:?}", ans);}
fn max_x(arr: &mut Vec<i32>) -> i32 {    if arr.len() < 2 {        return -1;    }    // 0 + arr[0]    let mut pre_best = arr[0];    let mut ans = 0;    for i in 1..arr.len() as i32 {        ans = get_max(ans, arr[i as usize] - i + pre_best);        pre_best = get_max(pre_best, arr[i as usize] + i);    }    return ans;}
fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {    if a > b {        a    } else {        b    }}