2023-08-30：用go語言編寫。兩個魔法卷軸問題。

給定一個數(shù)組arr，其中可能有正、負(fù)、0，

一個魔法卷軸可以把a(bǔ)rr中連續(xù)的一段全變成0，你希望數(shù)組整體的累加和盡可能大。

你有兩個魔法卷軸，請返回數(shù)組盡可能大的累加和。

1 <= arr長度 <= 100000，

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

來自微眾銀行。

來自左程云。

答案2023-08-30：

算法maxSum1：

1.定義一個輔助函數(shù)max，用于返回兩個數(shù)中的最大值。

2.定義函數(shù)maxSum1，接收一個整數(shù)數(shù)組arr作為參數(shù)，返回一個整數(shù)。

3.初始化變量p1為0，遍歷數(shù)組arr，累加每個元素到p1。

4.獲取數(shù)組arr的長度n。

5.調(diào)用函數(shù)mustOneScroll(arr, 0, n-1)，返回一個整數(shù)，并賦值給變量p2。

6.初始化變量p3為math.MinInt32。

7.循環(huán)變量i從1到n-1：

• ??調(diào)用函數(shù)mustOneScroll(arr, 0, i-1)，返回一個整數(shù)，并與調(diào)用函數(shù)mustOneScroll(arr, i, n-1)的返回值相加，得到一個新的整數(shù)。

• ??調(diào)用max函數(shù)，將p3與新整數(shù)比較，取較大值賦給p3。

8.調(diào)用max函數(shù)三次，分別比較p1、p2和p3的值，返回最大值作為結(jié)果。

算法maxSum2：

1.定義一個輔助函數(shù)max，用于返回兩個數(shù)中的最大值。

2.定義函數(shù)maxSum2，接收一個整數(shù)數(shù)組arr作為參數(shù)，返回一個整數(shù)。

3.如果數(shù)組arr的長度為0，直接返回0。

4.初始化變量p1為0，遍歷數(shù)組arr，累加每個元素到p1。

5.獲取數(shù)組arr的長度n。

6.創(chuàng)建長度為n的數(shù)組left，用于存儲每個位置左邊范圍內(nèi)的最大累加和。

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

8.循環(huán)變量i從1到n-1：

• ??將left[i]設(shè)置為max(left[i-1]+arr[i], maxSum)。

• ??累加arr[i]到sum。

• ??用max函數(shù)比較maxSum和sum的值，將較大值賦給maxSum。

9.創(chuàng)建長度為n的數(shù)組right，用于存儲每個位置右邊范圍內(nèi)的最大累加和。

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

11.倒序循環(huán)變量i從n-2到0：

-?將right[i]設(shè)置為max(arr[i]+right[i+1],?maxSum)。

-?累加arr[i]到sum。

-?用max函數(shù)比較maxSum和sum的值，將較大值賦給maxSum。

12.初始化變量p2為left[n-1]。

13.初始化變量p3為math.MinInt32。

14.循環(huán)變量i從1到n-1：

-?將left[i-1]+right[i]的值與p3比較，取較大值賦給p3。

15.調(diào)用max函數(shù)三次，分別比較p1、p2和p3的值，返回最大值作為結(jié)果。

時間復(fù)雜度和空間復(fù)雜度：

• ??對于maxSum1算法，時間復(fù)雜度為O(N^3)，其中N為數(shù)組arr的長度?？臻g復(fù)雜度為O(1)。

• ??對于maxSum2算法，時間復(fù)雜度為O(N)，其中N為數(shù)組arr的長度。空間復(fù)雜度為O(N)（需要額外的left和right數(shù)組）。

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
}

//?正式方法
//?時間復(fù)雜度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))
}

//?輔助函數(shù)，返回兩個數(shù)中的最大值
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("測試結(jié)束")
}


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
}

//?正式方法
//?時間復(fù)雜度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!("測試結(jié)束");
}


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?<<?"測試結(jié)束"?<<?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("測試結(jié)束\n");
????return?0;
}