首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2022-11-18:给定一个数组arr,表示连续n天的股价,数组下标表示第几天 指标X:任意两天的股价之和 - 此两天间隔的天数 比如 第3天,价格是10 第

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

原创
作者头像
福大大架构师每日一题
发布2022-11-18 21:39:01
3170
发布2022-11-18 21:39:01
举报

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
    }
}

执行结果如下:

在这里插入图片描述
在这里插入图片描述

左神java代码

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档