在本教程中,我们将讨论一个程序,以查找不包括某些元素的最大子数组总和。
为此,我们将提供两个大小为M和N的数组。我们的任务是在第一个数组中找到一个子数组,以使第二个数组中不存在该子数组中的元素,并且该子数组的元素总和为最大。
#include <bits/stdc++.h> using namespace std; //检查第二个数组中是否存在元素 bool isPresent(int B[], int m, int x) { for (int i = 0; i < m; i++) if (B[i] == x) return true; return false; } int findMaxSubarraySumUtil(int A[], int B[], int n, int m) { int max_so_far = INT_MIN, curr_max = 0; for (int i = 0; i < n; i++) { if (isPresent(B, m, A[i])) { curr_max = 0; continue; } curr_max = max(A[i], curr_max + A[i]); max_so_far = max(max_so_far, curr_max); } return max_so_far; } void findMaxSubarraySum(int A[], int B[], int n, int m) { int maxSubarraySum = findMaxSubarraySumUtil(A, B, n, m); if (maxSubarraySum == INT_MIN) { cout << "Maximum Subarray Sum cant be found" << endl; } else { cout << "The Maximum Subarray Sum = " << maxSubarraySum << endl; } } int main() { int A[] = { 3, 4, 5, -4, 6 }; int B[] = { 1, 8, 5 }; int n = sizeof(A) / sizeof(A[0]); int m = sizeof(B) / sizeof(B[0]); findMaxSubarraySum(A, B, n, m); return 0; }
输出结果
The Maximum Subarray Sum = 7