Tags:

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ụ:

Input: A = {1, 4, 6, 7, 9}, B = {4, 8, 9}
Output: 13

Ta xem các phần tử trong A mà có chứa trong B là một điểm khuyết, A = {1, !, 6, 7, ! }
Vậy ta có các mảng con của A là {1}, {6}, {7}, {6, 7} 
Ta thấy mảng con có tổng lớn {6, 7} nhất là 13

 

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;
    }
}
Output: Maximum Subarray Sum: 13

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

0 0 votes
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x