資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學在C++中，乘以任何子陣列的所有元素後最大化子陣列和
給定一個整數陣列和一個整數變數‘X’。任務是首先從給定陣列中形成子陣列，然後將子陣列的所有元素乘以整數X。最後找出貢獻最大和的元素。
讓我們看看各種輸入輸出場景 -
輸入 − int arr[] = {2, 4, 1, -5, -2}, X = 3
輸出 − 乘以任何子陣列的所有元素後最大化子陣列和的結果是：21
解釋 − 給定一個數組和一個整數變數X。首先，從給定陣列中獲取子陣列，例如{2, 4, 1}。現在將子陣列的所有元素乘以X，即3，所以陣列將變為{6, 12, 3, -5, -2}。最後，檢查最大子陣列和，它將返回6 + 12 + 3 = 21。
輸入 − int arr[] = {-1, 2, -6, 3, -4}, x= -1
輸出 − 乘以任何子陣列的所有元素後最大化子陣列和的結果是：11
解釋 − 給定一個數組和一個整數變數X。首先，從給定陣列中獲取子陣列，例如{-1, -6, -4}。現在將子陣列的所有元素乘以X，即-1，所以陣列將變為{1, 2, 6, 3, 4}。最後，檢查最大子陣列和，它將返回1 + 6 + 4 = 11。
下面程式中使用的方案如下
輸入一個整數陣列和一個整數變數作為‘X’。計算陣列的大小並將資料傳遞給函式Max_Subarray(arr, size, x)。
在函式Max_Subarray(arr, size, x)內部
宣告一個數組為int arr_2[size][3]和一個臨時變數temp為0。
使用C++中的memset()方法將陣列‘arr_2’的所有元素初始化為-1。
從i=0開始迴圈到陣列大小。在迴圈內，將temp設定為對函式max(temp, check(i, 0, arr, arr_2, size, x))的呼叫的結果。
返回temp。
在函式int check(int first, int last, int arr[], int arr_2[Max_size][3], int size, int x)內部
宣告一個臨時變數count為0。
檢查IF first = size，則返回0
檢查IF arr_2[first][last] != -1，則返回arr_2[first][last]。
檢查IF last = 0，則呼叫C++的內建max函式找出最大值，max(count, arr[first] + check(first + 1, 0, arr, arr_2, size, x))，並將count設定為max(count, x * arr[first] + check(first + 1, 1, arr, arr_2, size, x))
ELSE IF last = 1，則將count設定為max(count, x * arr[first] + check(first + 1, 1, arr, arr_2, size, x))，並將count設定為max(count, arr[first] + check(first + 1, 2, arr, arr_2, size, x))
ELSE，將count設定為max(count, arr[first] + check(first + 1, 2, arr, arr_2, size, x))；
將arr_2[first][last]返回到count。
列印結果。
示例
#include <bits/stdc++.h>
using namespace std;
#define Max_size 5
int check(int first, int last, int arr[], int arr_2[Max_size][3], int size, int x){
int count = 0;
if(first == size){
return 0;
}
if(arr_2[first][last] != -1){
return arr_2[first][last];}
if (last == 0){
count = max(count, arr[first] + check(first + 1, 0, arr, arr_2, size, x));
count = max(count, x * arr[first] + check(first + 1, 1, arr, arr_2, size, x));
}
else if(last == 1){
count = max(count, x * arr[first] + check(first + 1, 1, arr, arr_2, size, x));
count = max(count, arr[first] + check(first + 1, 2, arr, arr_2, size, x));
}
else{
count = max(count, arr[first] + check(first + 1, 2, arr, arr_2, size, x));
}
return arr_2[first][last] = count;
}
int Max_Subarray(int arr[], int size, int x){
int arr_2[size][3];
int temp = 0;
memset(arr_2, -1, sizeof arr_2);
for(int i = 0; i < size; i++){
temp = max(temp, check(i, 0, arr, arr_2, size, x));
}
return temp;
}
int main(){
int arr[] = {2, 4, 1, -5, -2};
int size = sizeof(arr) / sizeof(arr[0]);
int x = 3;
cout<<"Maximize the subarray sum after multiplying all elements of any subarray with X are: "<<Max_Subarray(arr, size, x);
return 0;
}輸出
如果執行以上程式碼，它將生成以下輸出
Maximize the subarray sum after multiplying all elements of any subarray with X are: 21
214 次檢視
