ผลรวมเซิร์บอาร์เรย์สูงสุดโดยตัดบางสมาชิกใน C++

ปัญหา

ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมเพื่อหาผลรวมเซิร์บอาร์เรย์สูงสุดโดยตัดบางสมาชิก

สำหรับนี้ เราจะได้รับอาร์เรย์สองอันขนาด M และ N งานของเราคือหาเซิร์บอาร์เรย์ในอาร์เรย์แรกโดยที่ไม่มีสมาชิกภายในเซิร์บอาร์เรย์อยู่ในอาร์เรย์ที่สอง และสมาชิกของเซิร์บอาร์เรย์บวกกันได้สูงสุด

ตัวอย่างโค้ด

#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; 
}

เอาต์พุต

The Maximum Subarray Sum = 7