2022-04-14：小美有一个长度为n的数组， 为了使得这个数组的和尽量大，她向会魔法的小团进行求助。 小团可以选择数组中至多两个不相交的子数组， 并将区间里的数全都变为原来的10倍。 小团想知道他

2022-04-14：小美有一个长度为n的数组，
为了使得这个数组的和尽量大，她向会魔法的小团进行求助。
小团可以选择数组中至多两个不相交的子数组，
并将区间里的数全都变为原来的10倍。
小团想知道他的魔法最多可以帮助小美将数组的和变大到多少?
来自美团。

答案2022-04-14：

动态规划。
时间复杂度：O(N)。
空间复杂度：O(N)。

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

#![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编写。代码如下：

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代码

2022-04-14：小美有一个长度为n的数组， 为了使得这个数组的和尽量大，她向会魔法的小团进行求助。 小团可以选择数组中至多两个不相交的子数组， 并将区间里的数全都变为原来的10倍。 小团想知道他的相关教程结束。