Tìm tổng lớn nhất của các mảng con chứa trong mảng A mà không chứa các phần tử của mảng B

Cho mảng A có N số nguyên và mảng B chứa M số nguyên. Tìm tổng lớn nhất của các mảng con trong A mà không chứa phần bất kỳ phần tử nào của B.

Ví dụ:

Trước khi làm bài này, chúng ta cần biết đến thuật toán Kadane’s Algorithm. Kadane’s Algorithm là thuật toán tính tổng lớn nhất của các mảng con. 

Note: Nếu giá trị trả về = 0, thì chuỗi con có tổng lớn nhất là {}.

public class Main {


    public static void main(String[] args) {
        int A[] = {1, 4, 6, 7, 9};
        int B[] = {4, 8, 9};

        int n = A.length;
        int m = B.length;

        System.out.println("Maximum Subarray Sum: " + maxSubArraySum(A, n, B, m));
    }

    public static boolean contain(int[] arr, int m, int value) {
        for (int item : arr) {
            if (item == value)
                return true;
        }
        return false;
    }

    static int maxSubArraySum(int a[], int n, int[] b, int m) {
        int max_so_far = Integer.MIN_VALUE, max_ending_here = 0;

        for (int i = 0; i < n; i++) {
            max_ending_here = max_ending_here + a[i];
            if (contain(b, m, a[i]))
                max_ending_here = 0;
            if (max_ending_here < 0)
                max_ending_here = 0;
            if (max_so_far < max_ending_here)
                max_so_far = max_ending_here;
        }
        return max_so_far;
    }
}

Độ phức tạp: θ(n * m)