V2AS问路
2023-08-30：用go语言编写。两个魔法卷轴问题。 给定一个数组arr，其中可能有正、负、0， 一个魔法卷轴可以把arr中连续的一段全变成0，你希望数组整体的累加和尽可能大。 你有两个魔法卷轴，
阅读原文时间：2023年08月31日阅读：1

2023-08-30：用go语言编写。两个魔法卷轴问题。

给定一个数组arr，其中可能有正、负、0，

一个魔法卷轴可以把arr中连续的一段全变成0，你希望数组整体的累加和尽可能大。

你有两个魔法卷轴，请返回数组尽可能大的累加和。

1 <= arr长度 <= 100000，

-100000 <= arr里的值 <= 100000。

来自微众银行。

来自左程云。

答案2023-08-30：

算法maxSum1：

1.定义一个辅助函数max，用于返回两个数中的最大值。

2.定义函数maxSum1，接收一个整数数组arr作为参数，返回一个整数。

3.初始化变量p1为0，遍历数组arr，累加每个元素到p1。

4.获取数组arr的长度n。

5.调用函数mustOneScroll(arr, 0, n-1)，返回一个整数，并赋值给变量p2。

6.初始化变量p3为math.MinInt32。

7.循环变量i从1到n-1：

  • 调用函数mustOneScroll(arr, 0, i-1)，返回一个整数，并与调用函数mustOneScroll(arr, i, n-1)的返回值相加，得到一个新的整数。

  • 调用max函数，将p3与新整数比较，取较大值赋给p3。

8.调用max函数三次，分别比较p1、p2和p3的值，返回最大值作为结果。

算法maxSum2：

1.定义一个辅助函数max，用于返回两个数中的最大值。

2.定义函数maxSum2，接收一个整数数组arr作为参数，返回一个整数。

3.如果数组arr的长度为0，直接返回0。

4.初始化变量p1为0，遍历数组arr，累加每个元素到p1。

5.获取数组arr的长度n。

6.创建长度为n的数组left，用于存储每个位置左边范围内的最大累加和。

7.初始化变量sum为arr[0]，maxSum为max(0, sum)。

8.循环变量i从1到n-1：

  • 将left[i]设置为max(left[i-1]+arr[i], maxSum)。

  • 累加arr[i]到sum。

  • 用max函数比较maxSum和sum的值，将较大值赋给maxSum。

9.创建长度为n的数组right，用于存储每个位置右边范围内的最大累加和。

10.初始化变量sum为arr[n-1]，maxSum为max(0, sum)。

11.倒序循环变量i从n-2到0：

- 将right[i]设置为max(arr[i]+right[i+1], maxSum)。

- 累加arr[i]到sum。

- 用max函数比较maxSum和sum的值，将较大值赋给maxSum。

12.初始化变量p2为left[n-1]。

13.初始化变量p3为math.MinInt32。

14.循环变量i从1到n-1：

- 将left[i-1]+right[i]的值与p3比较，取较大值赋给p3。

15.调用max函数三次，分别比较p1、p2和p3的值，返回最大值作为结果。

时间复杂度和空间复杂度：

  • 对于maxSum1算法，时间复杂度为O(N^3)，其中N为数组arr的长度。空间复杂度为O(1)。

  • 对于maxSum2算法，时间复杂度为O(N)，其中N为数组arr的长度。空间复杂度为O(N)（需要额外的left和right数组）。

go完整代码如下：

package main

import (
    "fmt"
    "math"
    "math/rand"
    "time"
)

// 暴力方法
// 为了测试
func maxSum1(arr []int) int {
    p1 := 0
    for _, num := range arr {
        p1 += num
    }
    n := len(arr)
    p2 := mustOneScroll(arr, 0, n-1)
    p3 := math.MinInt32
    for i := 1; i < n; i++ {
        p3 = max(p3, mustOneScroll(arr, 0, i-1)+mustOneScroll(arr, i, n-1))
    }
    return max(p1, max(p2, p3))
}

// 为了测试
func mustOneScroll(arr []int, L, R int) int {
    ans := math.MinInt32
    for a := L; a <= R; a++ {
        for b := a; b <= R; b++ {
            curAns := 0
            for i := L; i < a; i++ {
                curAns += arr[i]
            }
            for i := b + 1; i <= R; i++ {
                curAns += arr[i]
            }
            ans = max(ans, curAns)
        }
    }
    return ans
}

// 正式方法
// 时间复杂度O(N)
func maxSum2(arr []int) int {
    if len(arr) == 0 {
        return 0
    }
    // 一个卷轴也不用
    p1 := 0
    for _, num := range arr {
        p1 += num
    }
    n := len(arr)
    // left[i] : 0 ~ i范围上，一定要用一次卷轴的情况下，最大累加和多少
    left := make([]int, n)
    // left[0] = 0 : 0 ~ 0，一定要用一次卷轴的情况下，最大累加和多少
    // 每一步的前缀和
    // 0~0 前缀和
    sum := arr[0]
    // 之前所有前缀和的，最大值
    maxSum := max(0, sum)
    for i := 1; i < n; i++ {
        // left[i - 1] + arr[i]
        // maxSum : 之前所有前缀和的，最大值
        left[i] = max(left[i-1]+arr[i], maxSum)
        sum += arr[i]
        maxSum = max(maxSum, sum)
    }
    // 只用一次卷轴，必须用，0~n-1范围上的解，第二种可能性
    p2 := left[n-1]
    // 第三种 ：一定要用两次卷轴
    right := make([]int, n)
    // right[i] : i ~ n-1范围上，一定要用一次卷轴的情况下，最大累加和多少
    sum = arr[n-1]
    maxSum = max(0, sum)
    for i := n - 2; i >= 0; i-- {
        right[i] = max(arr[i]+right[i+1], maxSum)
        sum += arr[i]
        maxSum = max(maxSum, sum)
    }
    p3 := math.MinInt32
    for i := 1; i < n; i++ {
        // 0..0 1...n-1
        // 0..1 2...n-1
        // 0..2 3...n-1
        p3 = max(p3, left[i-1]+right[i])
    }
    return max(p1, max(p2, p3))
}

// 辅助函数，返回两个数中的最大值
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

// 为了测试
func randomArray(n, v int) []int {
    arr := make([]int, n)
    rand.Seed(time.Now().UnixNano())
    for i := 0; i < n; i++ {
        arr[i] = rand.Intn(2*v+1) - v
    }
    return arr
}

func main() {
    rand.Seed(time.Now().UnixMilli())
    N := 50
    V := 100
    testTimes := 10000
    fmt.Println("测试开始")
    for i := 0; i < testTimes; i++ {
        n := rand.Intn(N)
        arr := randomArray(n, V)
        ans1 := maxSum1(arr)
        ans2 := maxSum2(arr)
        if ans1 != ans2 {
            fmt.Println("出错了!")
        }
    }
    fmt.Println("测试结束")
}

rust完整代码如下：

use std::cmp;

// 暴力方法
// 为了测试
fn max_sum1(arr: &[i32]) -> i32 {
    let mut p1 = 0;
    for &num in arr {
        p1 += num;
    }
    let n = arr.len() as i32;
    let mut p2 = must_one_scroll(arr, 0, n - 1);
    let mut p3 = i32::MIN;
    for i in 1..n {
        p3 = cmp::max(
            p3,
            must_one_scroll(arr, 0, i - 1) + must_one_scroll(arr, i, n - 1),
        );
    }
    cmp::max(p1, cmp::max(p2, p3))
}

// 为了测试
fn must_one_scroll(arr: &[i32], l: i32, r: i32) -> i32 {
    let mut ans = i32::MIN;
    for a in l..=r {
        for b in a..=r {
            let mut cur_ans = 0;
            for i in l..a {
                cur_ans += arr[i as usize];
            }
            for i in b + 1..=r {
                cur_ans += arr[i as usize];
            }
            ans = cmp::max(ans, cur_ans);
        }
    }
    ans
}

// 正式方法
// 时间复杂度O(N)
fn max_sum2(arr: &[i32]) -> i32 {
    if arr.is_empty() {
        return 0;
    }
    // 一个卷轴也不用
    let mut p1 = 0;
    for &num in arr {
        p1 += num;
    }
    let n = arr.len() as i32;
    // left[i] : 0 ~ i范围上，一定要用一次卷轴的情况下，最大累加和多少
    let mut left = vec![0; n as usize];
    // left[0] = 0 : 0 ~ 0，一定要用一次卷轴的情况下，最大累加和多少
    // 每一步的前缀和
    // 0~0 前缀和
    let mut sum = arr[0];
    // 之前所有前缀和的，最大值
    let mut max_sum = cmp::max(0, sum);
    for i in 1..n {
        // left[i - 1] + arr[i]
        // max_sum : 之前所有前缀和的，最大值
        left[i as usize] = cmp::max(left[i as usize - 1] + arr[i as usize], max_sum);
        sum += arr[i as usize];
        max_sum = cmp::max(max_sum, sum);
    }
    // 只用一次卷轴，必须用，0~n-1范围上的解，第二种可能性
    let p2 = left[n as usize - 1];
    // 第三种 ：一定要用两次卷轴
    let mut right = vec![0; n as usize];
    // right[i] : i ~ n-1范围上，一定要用一次卷轴的情况下，最大累加和多少
    sum = arr[n as usize - 1];
    max_sum = cmp::max(0, sum);
    for i in (0..n - 1).rev() {
        right[i as usize] = cmp::max(arr[i as usize] + right[i as usize + 1], max_sum);
        sum += arr[i as usize];
        max_sum = cmp::max(max_sum, sum);
    }
    let mut p3 = i32::MIN;
    for i in 1..n {
        // 0..0 1...n-1
        // 0..1 2...n-1
        // 0..2 3...n-1
        p3 = cmp::max(p3, left[i as usize - 1] + right[i as usize]);
    }
    cmp::max(p1, cmp::max(p2, p3))
}

// 为了测试
fn random_array(n: usize, v: i32) -> Vec<i32> {
    let mut arr = vec![0; n];
    for i in 0..n {
        arr[i] = (rand::random::<i32>() % (v * 2 + 1)) - v;
    }
    arr
}

// 为了测试
fn main() {
    let n = 50;
    let v = 100;
    let test_times = 10_000;
    println!("测试开始");
    for _ in 0..test_times {
        let n = rand::random::<usize>() % n;
        let arr = random_array(n, v);
        let ans1 = max_sum1(&arr);
        let ans2 = max_sum2(&arr);
        if ans1 != ans2 {
            println!("出错了!");
        }
    }
    println!("测试结束");
}

c++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int mustOneScroll(vector<int>& arr, int L, int R) {
    int ans = INT_MIN;
    for (int a = L; a <= R; a++) {
        for (int b = a; b <= R; b++) {
            int curAns = 0;
            for (int i = L; i < a; i++) {
                curAns += arr[i];
            }
            for (int i = b + 1; i <= R; i++) {
                curAns += arr[i];
            }
            ans = max(ans, curAns);
        }
    }
    return ans;
}

int maxSum1(vector<int>& arr) {
    int p1 = 0;
    for (int num : arr) {
        p1 += num;
    }
    int n = arr.size();
    int p2 = mustOneScroll(arr, 0, n - 1);
    int p3 = INT_MIN;
    for (int i = 1; i < n; i++) {
        p3 = max(p3, mustOneScroll(arr, 0, i - 1) + mustOneScroll(arr, i, n - 1));
    }
    return max(p1, max(p2, p3));
}

int maxSum2(vector<int>& arr) {
    if (arr.size() == 0) {
        return 0;
    }
    int p1 = 0;
    for (int num : arr) {
        p1 += num;
    }
    int n = arr.size();
    vector<int> left(n);
    int sum = arr[0];
    int maxSum = max(0, sum);
    for (int i = 1; i < n; i++) {
        left[i] = max(left[i - 1] + arr[i], maxSum);
        sum += arr[i];
        maxSum = max(maxSum, sum);
    }
    int p2 = left[n - 1];
    vector<int> right(n);
    sum = arr[n - 1];
    maxSum = max(0, sum);
    for (int i = n - 2; i >= 0; i--) {
        right[i] = max(arr[i] + right[i + 1], maxSum);
        sum += arr[i];
        maxSum = max(maxSum, sum);
    }
    int p3 = INT_MIN;
    for (int i = 1; i < n; i++) {
        p3 = max(p3, left[i - 1] + right[i]);
    }
    return max(p1, max(p2, p3));
}

vector<int> randomArray(int n, int v) {
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        arr[i] = rand() % (2 * v + 1) - v;
    }
    return arr;
}

int main() {
    int N = 50;
    int V = 100;
    int testTimes = 10000;
    cout << "测试开始" << endl;
    for (int i = 0; i < testTimes; i++) {
        int n = rand() % N;
        vector<int> arr = randomArray(n, V);
        int ans1 = maxSum1(arr);
        int ans2 = maxSum2(arr);
        if (ans1 != ans2) {
            cout << "出错了!" << endl;
        }
    }
    cout << "测试结束" << endl;
    return 0;
}

c完整代码如下：

#include <stdio.h>
#include <stdlib.h>

int maxSum1(int* arr, int n);
int mustOneScroll(int* arr, int L, int R);
int maxSum2(int* arr, int n);
int* randomArray(int n, int v);

int maxSum1(int* arr, int n) {
    int p1 = 0;
    int* ptr = arr;
    for (int i = 0; i < n; i++) {
        p1 += *ptr++;
    }
    int p2 = mustOneScroll(arr, 0, n - 1);
    int p3 = -INT_MAX;
    for (int i = 1; i < n; i++) {
        p3 = (p3 > mustOneScroll(arr, 0, i - 1) + mustOneScroll(arr, i, n - 1)) ? p3 : mustOneScroll(arr, 0, i - 1) + mustOneScroll(arr, i, n - 1);
    }
    return (p1 > (p2 > p3 ? p2 : p3)) ? p1 : ((p2 > p3) ? p2 : p3);
}

int mustOneScroll(int* arr, int L, int R) {
    int ans = -INT_MAX;
    for (int a = L; a <= R; a++) {
        for (int b = a; b <= R; b++) {
            int curAns = 0;
            for (int i = L; i < a; i++) {
                curAns += *(arr + i);
            }
            for (int i = b + 1; i <= R; i++) {
                curAns += *(arr + i);
            }
            ans = (ans > curAns) ? ans : curAns;
        }
    }
    return ans;
}

int maxSum2(int* arr, int n) {
    if (n == 0) {
        return 0;
    }
    int p1 = 0;
    int* ptr = arr;
    for (int i = 0; i < n; i++) {
        p1 += *ptr++;
    }
    int* left = (int*)malloc(n * sizeof(int));
    int* right = (int*)malloc(n * sizeof(int));
    int sum, maxSum;

    sum = *arr;
    maxSum = (0 > sum) ? 0 : sum;
    *left = (0 > (*arr)) ? 0 : (*arr);
    for (int i = 1; i < n; i++) {
        *(left + i) = (*(left + i - 1) + *(arr + i) > maxSum) ? *(left + i - 1) + *(arr + i) : maxSum;
        sum += *(arr + i);
        maxSum = (maxSum > sum) ? maxSum : sum;
    }

    int p2 = *(left + (n - 1));

    sum = *(arr + (n - 1));
    maxSum = (0 > sum) ? 0 : sum;
    *(right + (n - 1)) = (0 > (*(arr + (n - 1)))) ? 0 : (*(arr + (n - 1)));
    for (int i = n - 2; i >= 0; i--) {
        *(right + i) = (*(arr + i) + *(right + i + 1) > maxSum) ? (*(arr + i) + *(right + i + 1)) : maxSum;
        sum += *(arr + i);
        maxSum = (maxSum > sum) ? maxSum : sum;
    }

    int p3 = -INT_MAX;
    for (int i = 1; i < n; i++) {
        p3 = (p3 > (*(left + i - 1) + *(right + i))) ? p3 : (*(left + i - 1) + *(right + i));
    }

    int result = (p1 > (p2 > p3 ? p2 : p3)) ? p1 : ((p2 > p3) ? p2 : p3);

    free(left);
    free(right);

    return result;
}

int* randomArray(int n, int v) {
    int* arr = (int*)malloc(n * sizeof(int));
    int* ptr = arr;
    for (int i = 0; i < n; i++) {
        *ptr++ = (rand() % (2 * v + 1)) - v;
    }
    return arr;
}

int main() {
    int N = 50;
    int V = 100;
    int testTimes = 10000;
    printf("测试开始\n");
    for (int i = 0; i < testTimes; i++) {
        int n = rand() % N;
        int* arr = randomArray(n, V);
        int ans1 = maxSum1(arr, n);
        int ans2 = maxSum2(arr, n);
        if (ans1 != ans2) {
            printf("出错了!\n");
        }
        free(arr);
    }
    printf("测试结束\n");
    return 0;
}

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章

2023-08-24：请用go语言编写。给定一个长度为n的数组arr， 现在你有一次机会, 将其中连续的K个数全修改成任意一个值， 请你计算如何修改可以使修改后的数 列的最长不下降子序列最长。 请输出
2023-08-20：用go语言写算法。给定一个由'W'、'A'、'S'、'D'四种字符组成的字符串，长度一定是4的倍数， 你可以把任意连续的一段子串，变成'W'、'A'、'S'、'D'组成的随意状
Go语言学习总结

4

2023-06-20：给定一个长度为N的数组arr，arr[i]表示宝石的价值 你在某天遇到X价值的宝石， X价值如果是所有剩余宝石价值中的最小值，你会将该宝石送人 X价值如果不是所有剩余宝石价值中的

5

Rust的类型系统

6

2023-05-21：给定一个字符串 s 和一个整数 k 。你可以从 s 的前 k 个字母中选择一个， 并把它加到字符串的末尾。 返回 在应用上述步骤的任意数量的移动后，字典上最小的字符串。 输入：s

7

【Netty】01 - NIO

8

jdk8-stream-api

9

三种方法求解最大子区间和：DP、前缀和、分治

10

JavaSE23-函数式接口&Stream流