Tổng mảng con tối đa không bao gồm các phần tử nhất định trong C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để tìm Tổng của mảng con tối đa loại trừ các phần tử nhất định.

Đối với điều này, chúng ta sẽ được cung cấp hai mảng có kích thước M và N. Nhiệm vụ của chúng ta là tìm một mảng con trong mảng đầu tiên sao cho không có phần tử nào bên trong mảng con có mặt bên trong mảng thứ hai và các phần tử của mảng con tổng hợp lại là tối đa.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
//checking if element is present in second array
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;
}

Đầu ra

The Maximum Subarray Sum = 7