前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2022-04-14:小美有一个长度为n的数组,为了使得这个数组的和尽量大,她向会魔法的小团进行求助。

2022-04-14:小美有一个长度为n的数组,为了使得这个数组的和尽量大,她向会魔法的小团进行求助。

作者头像
福大大架构师每日一题
发布2022-06-04 10:31:39
4050
发布2022-06-04 10:31:39
举报

2022-04-14:小美有一个长度为n的数组,

为了使得这个数组的和尽量大,她向会魔法的小团进行求助。

小团可以选择数组中至多两个不相交的子数组,

并将区间里的数全都变为原来的10倍。

小团想知道他的魔法最多可以帮助小美将数组的和变大到多少?

来自美团。

答案2022-04-14:

动态规划。

时间复杂度:O(N)。

空间复杂度:O(N)。

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

代码语言:javascript
复制
#![feature(core_intrinsics)]
fn print_type_of<T>(_: T) {
    println!("{}", unsafe { std::intrinsics::type_name::<T>() });
}

fn main(){
    let arr: Vec<i32> = vec![3, -4, 5, 1, -3];
    let ret:i32 = max_sum2(arr);
    println!("{}",ret);
    print_type_of(ret);
}


fn max_sum2(arr: Vec<i32>) ->i32 {
  let n = arr.len();
  if n == 0 {
    return 0;
  }
  if n == 1 {
    return get_max(arr[0], arr[0]*10);
  }
  // dp[i]
  // 1) arr[0...i]原始累加和
  // 2) dp[i-1] + arr[i]
  // 3) magic[i]

  // : arr[0..i]范围上,可以没有10倍区域、或者有10倍区域但是最多有一个的情况下,
  //    最大累加和是多少?
  // 可能性1:就是没有10倍区域,那就是arr[0..i]的累加和, 这个好弄!
  //
  // 可能性2:有一个10倍区域
  //         a : arr[i]不在10倍区域里,但是之前可能有,那么就是dp[i-1] + arr[i]
  //
  //         b : arr[i]在10倍区域里
  //             甲:arr[0..i-1]没有10倍区域,arr[i]自己10倍,arr[0..i-1] + 10 * arr[i]
  //             乙:arr[0..i-1]中i-1位置在10倍区域里,arr[i]也在10倍区域里
  // magic[i] : magic[i] ..i  i
  // 对于乙,要求知道magic[j]的信息
  // magic[j]:arr[0..j]范围上,j一定要在10倍区域里,并且只有一个10倍区域的情况下,最大累加和
  // 可能性1:只有arr[j]是10倍,arr[0..j-1]没有10倍
  // 可能性2:magic[j-1] + 10 * arr[j]
  let mut sum :i32 = arr[(n-1) as usize];
  let mut magic:i32 = sum * 10;
    let mut right:Vec<i32> = Vec::new(); 
    for i in 0..n { 
        right.push(0); 
    } 
    
  right[n-1] = get_max(sum, sum*10);

    let mut i:isize=n as isize -2 as isize;
  while i >= 0 {
    magic = 10*arr[i as usize] + get_max(sum, magic);
    sum = sum + arr[i as usize];
    right[i as usize] = get_max(get_max(sum, right[i as usize + 1] + arr[i as usize]), magic);
        i = i - 1;
  }
  let mut ans:i32 = right[0];
  sum = arr[0];
  magic = sum * 10;
  let mut dp:i32 = get_max(sum, sum * 10);
  ans = get_max(ans, dp + right[1]);
    i=1;
  while i < n as isize-1{
    magic = 10 * arr[i as usize] + get_max(sum, magic);
    sum = sum + arr[i as usize];
    dp = get_max(get_max(sum, dp+arr[i as usize]), magic);
    ans = get_max(ans, dp + right[i as usize + 1]);
        i = i + 1;
  }
  return ans;
}

fn get_max(a:i32, b :i32) ->i32 {
  if a > b {a} else {b}
}

执行结果如下:

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

代码语言:javascript
复制
package main

import "fmt"

func main() {
  arr := []int{3, -4, 5, 1, -3}
  ret := maxSum2(arr)
  fmt.Println(ret)
}

func maxSum2(arr []int) int {
  n := len(arr)
  if n == 0 {
    return 0
  }
  if n == 1 {
    return getMax(arr[0], arr[0]*10)
  }
  // dp[i]
  // 1) arr[0...i]原始累加和
  // 2) dp[i-1] + arr[i]
  // 3) magic[i]

  // : arr[0..i]范围上,可以没有10倍区域、或者有10倍区域但是最多有一个的情况下,
  //    最大累加和是多少?
  // 可能性1:就是没有10倍区域,那就是arr[0..i]的累加和, 这个好弄!
  //
  // 可能性2:有一个10倍区域
  //         a : arr[i]不在10倍区域里,但是之前可能有,那么就是dp[i-1] + arr[i]
  //
  //         b : arr[i]在10倍区域里
  //             甲:arr[0..i-1]没有10倍区域,arr[i]自己10倍,arr[0..i-1] + 10 * arr[i]
  //             乙:arr[0..i-1]中i-1位置在10倍区域里,arr[i]也在10倍区域里
  // magic[i] : magic[i] ..i  i
  // 对于乙,要求知道magic[j]的信息
  // magic[j]:arr[0..j]范围上,j一定要在10倍区域里,并且只有一个10倍区域的情况下,最大累加和
  // 可能性1:只有arr[j]是10倍,arr[0..j-1]没有10倍
  // 可能性2:magic[j-1] + 10 * arr[j]
  sum := arr[n-1]
  magic := sum * 10
  right := make([]int, n)
  right[n-1] = getMax(sum, sum*10)
  for i := n - 2; i >= 0; i-- {
    magic = 10*arr[i] + getMax(sum, magic)
    sum += arr[i]
    right[i] = getMax(getMax(sum, right[i+1]+arr[i]), magic)
  }
  ans := right[0]
  sum = arr[0]
  magic = sum * 10
  dp := getMax(sum, sum*10)
  ans = getMax(ans, dp+right[1])
  for i := 1; i < n-1; i++ {
    magic = 10*arr[i] + getMax(sum, magic)
    sum += arr[i]
    dp = getMax(getMax(sum, dp+arr[i]), magic)
    ans = getMax(ans, dp+right[i+1])
  }
  return ans
}

func getMax(a, b int) int {
  if a > b {
    return a
  } else {
    return b
  }
}

执行结果如下:

***

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

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

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

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

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

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