前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2022-05-25:最大子段和是一个经典问题,即对于一个数组找出其和最大的子数组。现在允许你在求解该问题之前翻转这个数組的连续

2022-05-25:最大子段和是一个经典问题,即对于一个数组找出其和最大的子数组。现在允许你在求解该问题之前翻转这个数組的连续

作者头像
福大大架构师每日一题
发布2022-06-04 11:06:04
3870
发布2022-06-04 11:06:04
举报

2022-05-25:最大子段和是

一个经典问题,即对于一个数组找出其和最大的子数组。

现在允许你在求解该问题之前翻转这个数組的连续一段,

如翻转(1,2,3,4,5,6)的第三个到第五个元素組成的子数组得到的是(1,2,5,4,3,6),

则翻转后该数组的最大子段和最大能达到多少?

来自字节,

几乎一样的题,来自字节笔试第4题。

给定两个数組values和numbers,

values[i]表示i号宝石的单品价值,

numbers[i]表示i号宝石的数量,

i号宝石的总价值 = values[i] * numbers[i]。

如果有一种魔法,可以翻转任何区间L...R的宝石,也就是改变L..R的宝石排列,变成逆序的。

求在允许用一次魔法的情况下,任取一段连续区间,能达到的最大价值。

这两个问法解法都几乎一样,区别无非是:

美团的: 可进行一次翻转情况下,子数组最大累加和;

字节的: 可进行一次翻转情况下,子数组最大价值和。

来自美团。

答案2022-05-25:

从左往右:dp[i]左=max(arr[i],dp[i-1]+arr[i])

从右往左:dp[i]右

逆序的这段,既不会贯穿,也不会在内部。也就说会选择逆序的一部分,只有这种可能。

左+部分逆序 等价于 右+部分逆序。

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

代码语言:javascript
复制
use rand::Rng;
fn main() {
    let len: i32 = 5;
    let value: i32 = 20;
    let test_time: i32 = 20000;
    println!("测试开始");
    for _i in 0..test_time {
        let n: i32 = rand::thread_rng().gen_range(0, len) + 1;
        let mut arr = random_array(n, value);
        let ans1 = max_sum_reverse1(&mut arr);
        let ans2 = max_sum_reverse2(&mut arr);
        if ans1 != ans2 {
            println!("出错了!");
            for num in &arr {
                print!("{} ", num);
            }
            println!("");
            println!("ans1 = {}", ans1);
            println!("ans2 = {}", ans2);
            break;
        }
    }
    println!("测试结束");
}

fn max_sum_reverse1(arr: &mut Vec<i32>) -> i32 {
    let mut ans: i32 = i32::min_value();
    for l in 0..arr.len() as i32 {
        for r in l..arr.len() as i32 {
            reverse(arr, l, r);
            ans = get_max(ans, max_sum(arr));
            reverse(arr, l, r);
        }
    }
    return ans;
}

fn reverse(arr: &mut Vec<i32>, mut l: i32, mut r: i32) {
    while l < r {
        let tmp = arr[l as usize];
        arr[l as usize] = arr[r as usize];
        l += 1;
        arr[r as usize] = tmp;
        r -= 1;
    }
}

fn max_sum(arr: &mut Vec<i32>) -> i32 {
    let mut pre = arr[0];
    let mut max = arr[0];
    for i in 1..arr.len() as i32 {
        pre = get_max(arr[i as usize], arr[i as usize] + pre);
        max = get_max(max, pre);
    }
    return max;
}

fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a > b {
        a
    } else {
        b
    }
}

fn max_sum_reverse2(arr: &mut Vec<i32>) -> i32 {
    let n = arr.len() as i32;
    let mut prefix: Vec<i32> = vec![];
    for _i in 0..n {
        prefix.push(0)
    }
    prefix[(n - 1) as usize] = arr[(n - 1) as usize];
    let mut i: i32 = n - 2;
    while i >= 0 {
        prefix[i as usize] = arr[i as usize] + get_max(0, prefix[(i + 1) as usize]);
        i -= 1;
    }
    let mut ans = prefix[0];
    let mut suffix = arr[0];
    let mut max_suffix = suffix;
    for i in 1..n {
        ans = get_max(ans, max_suffix + prefix[i as usize]);
        suffix = arr[i as usize] + get_max(0, suffix);
        max_suffix = get_max(max_suffix, suffix);
    }
    ans = get_max(ans, max_suffix);
    return ans;
}

// 为了测试
fn random_array(n: i32, v: i32) -> Vec<i32> {
    let mut arr: Vec<i32> = vec![];
    for _i in 0..n {
        arr.push(rand::thread_rng().gen_range(0, v) - rand::thread_rng().gen_range(0, v));
    }
    return arr;
}

执行结果如下:

***

[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_03_3_week/Code03_MaxSumOnReverseArray.java)

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-05-25,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 福大大架构师每日一题 微信公众号,前往查看

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

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

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