Trong bài toán này, chúng ta được cung cấp một mảng các số nguyên (dương cũng như âm). Nhiệm vụ của chúng tôi là tạo một chương trình để tính toán ProductSubarray tối đa trong C ++.
Giải pháp vấn đề - Ở đây, chúng ta có một mảng chứa các số dương, số âm và số 0. Chúng ta cần tìm tích của các mảng con được tạo bởi các phần tử của mảng. Và tối đa hóa sản phẩm của mảng con.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {-1, 2, -7, -5, 12, 6} Đầu ra
5040
Giải thích
Mảng con có sản phẩm tối đa là {2, -7, -5, 12, 6}
Product = 5040
Phương pháp tiếp cận giải pháp
Để giải quyết vấn đề này, chúng ta được cung cấp một mảng và tích tối đa của mảng con và quản lý maxVal là sản phẩm tối đa cho đến phần tử hiện tại và minVal là cực đại âm của sản phẩm. Sau đó, dựa trên giá trị hiện tại, maxVal và minVal được cập nhật thành -
Trường hợp 1 - Phần tử là tích cực - Cập nhật maxVal và minVal bằng cách nhân mảng.
Trường hợp 2 - Phần tử là 0 - Ngắt mảng con hiện tại vì nhân với 0 sẽ cho kết quả là 0.
Trường hợp 3 - Phần tử là phủ định - Cập nhật Cả hai giá trị bằng các giá trị âm làm giá trị cực đại của nó.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#include <iostream>
using namespace std;
int min(int a, int b){
if(a < b)
return a;
return b;
}
int max(int a, int b){
if(a > b)
return a;
return b;
}
int CalcMaxProductSubArray(int arr[], int n) {
int i = 0;
int maxVal = -1000;
int localMax = 1;
int localMin = 1;
int lastMax;
while(i < n) {
int currentVal = arr[i];
if (currentVal > 0) {
localMax = (localMax * currentVal);
localMin = min(1, localMin * currentVal);
}
else if (currentVal < 0) {
lastMax = localMax;
localMax = (localMin * currentVal);
localMin = (lastMax * currentVal);
} else {
localMin = 1;
localMax = 0;
}
maxVal = max(maxVal, localMax);
if (localMax <= 0)
localMax = 1;
i++;
}
return maxVal;
}
int main(){
int arr[] = { -1, 2, -7, -5, 12, 6 };
int n = 6;
cout<<"The maximum product Subarray is "<<CalcMaxProductSubArray(arr, n);
return 0;
} Đầu ra
The maximum product Subarray is 5040