Tìm tổng cân bằng tối đa trong mảng

Cho một mảng arr[] có size = N. Tìm tổng cân bằng lớn nhất tại i sao cho Sum(arr[0…i]) = Sum(arr[i…N-1). Nếu không có điểm i nào thoả điều kiện thì trả về -1.

Ví dụ

Ý tưởng đầu tiên và dễ làm nhất là dùng 2 vòng Loop

class Main {

    static int findMaxSum(int []arr, int n)
    {
        int res = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++)
        {
            int prefix_sum = arr[i];

            for (int j = 0; j < i; j++)
                prefix_sum += arr[j];

            int suffix_sum = arr[i];

            for (int j = n - 1; j > i; j--)
                suffix_sum += arr[j];

            if (prefix_sum == suffix_sum)
                res = Math.max(res, prefix_sum);
        }

        return res;
    }

    public static void main (String[] args)
    {
        int arr[] = {-1, 2, 5, 1, 5, 2, -1};
        int n = arr.length;
        int result = findMaxSum(arr, n);
        if (result == Integer.MIN_VALUE)
            System.out.println("Khong tim thay");
        else
            System.out.println(findMaxSum(arr, n));
    }
}

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

Mình có cách khác như này, ta sẽ xem Loop qua một lượt để tính từng giá sumPre và sumSuf ứng với mỗi vị trí trong mảng.  Sau đó đem đi so sánh để tìm ra kết quả

class Main {

    static int findMaxSum(int[] arr, int n) {
        int[] preSum = new int[n];

        int[] suffSum = new int[n];

        int result = Integer.MIN_VALUE;

        preSum[0] = arr[0];
        for (int i = 1; i < n; i++)
            preSum[i] = preSum[i - 1] + arr[i];

        suffSum[n - 1] = arr[n - 1];

        if (preSum[n - 1] == suffSum[n - 1])
            result = Math.max(result, preSum[n - 1]);

        for (int i = n - 2; i >= 0; i--) {
            suffSum[i] = suffSum[i + 1] + arr[i];

            if (suffSum[i] == preSum[i])
                result = Math.max(result, preSum[i]);
        }

        return result;
    }

    public static void main(String[] args) {
        int arr[] = {-1, 2, 5, 1, 5, 2, -1};
        int n = arr.length;
        int result = findMaxSum(arr, n);
        if (result == Integer.MIN_VALUE)
            System.out.println("Khong tim thay");
        else
            System.out.println(findMaxSum(arr, n));
    }
}

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

Cách sau đã được optimize, làm giảm độ phức tạp đi rất đáng kể. Một điểm chính mình cần lưu ý là cách này sẽ bỏ đi những phép  tính tổng dư lừa mà cách 1 làm.

Nguồn tham khảo: geeksforgeeks