maximum subarray product
#include <iostream>
#include <vector>
#include <limits>
using namespace std;
// Function to calculate the sum of elements in the given range [start, end]
int range_sum(const vector<int>& arr, int start, int end) {
int sum = 0;
for (int i = start; i <= end; ++i) {
sum += arr[i];
}
return sum;
}
// Function to calculate the sum of elements outside the range [start, end]
int remaining_sum(const vector<int>& arr, int start, int end) {
int sum = 0;
for (int i = 0; i < start; ++i) {
sum += arr[i];
}
for (int i = end + 1; i < arr.size(); ++i) {
sum += arr[i];
}
return sum;
}
// Function to find the contiguous subarray that maximizes the product
tuple<int, int, int> maximize_subarray_product(const vector<int>& arr) {
int n = arr.size();
if (n < 2) {
return {0, 0, 0}; // If the array has less than 2 elements, return 0s
}
int max_product = numeric_limits<int>::min(); // Initialize max product to
negative infinity
int result_start = 0;
int result_end = 0;
// Iterate over all possible subarrays
for (int start = 0; start < n; ++start) {
for (int end = start; end < n; ++end) {
int subarray_sum = range_sum(arr, start, end); // Sum of elements in
the subarray
int remaining = remaining_sum(arr, start, end); // Sum of remaining
elements
int current_product = subarray_sum * remaining; // Calculate the
product
// Update max_product and indices if a better product is found
if (current_product > max_product ||
(current_product == max_product && start < result_start)) {
max_product = current_product;
result_start = start;
result_end = end;
}
}
}
return {max_product, result_start, result_end};
}
int main() {
int n;
cout << "Enter the size of the array: ";
cin >> n;
vector<int> arr(n);
cout << "Enter the elements of the array: ";
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
auto [max_product, start, end] = maximize_subarray_product(arr); // Call the
function
cout << "Maximum Product: " << max_product << endl;
cout << "Start Index: " << start << ", End Index: " << end << endl;
return 0;
}
