Tìm tổng lớn nhất từ 3 phần tử trong mảng

Cho mảng số nguyên arr có số lượng phần tử n(n >= 3) . Tìm tổng lớn nhất từ 3 phần tử trong mảng. 

Ví dụ

Input: arr[] = {1, 3, 7, 2, 10, 5}, n = 6
Output: 22 (10 + 7 + 5)

Cách 1: Basic 

Cách đầu tiên cũng là cách đơn giản nhất, sử dụng 3 vòng loop để lấy toàn bộ tổng của 3 số có thể có trong mảng và rút ra kết quả.

public class Main {

    public static int maxSumTriplet(int[] arr, int n) {
        int sum = Integer.MIN_VALUE;
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (sum < arr[i] + arr[j] + arr[k])
                        sum = arr[i] + arr[j] + arr[k];
                }
            }
        }
        return sum;
    }
    public static void main(String[] args) {
        int[] arr = {1, 3, 7, 2, 10, 5};
        System.out.println(maxSumTriplet(arr, arr.length));
    }
}

Output: 22

Độ phức tạp: O(n³)

Cách 2: Sắp xếp

Với cách 1 chúng ta đã tốn đến O(n³) như vậy là quá tốn thời gian phải không nào? Chúng ta nhận xét một xíu nhé. Để có tổng lớn nhất từ 3 phần tử trong mảng thì 3 phần tử đó phải là 3 phần tử lớn nhất theo thứ tự 1,2,3 (có thể đồng hạng).

Mình sẽ sử dụng hàm Sort của java cung cấp sẵn. Nếu các bạn chưa có kiến thức về sắp xếp thì có thể xem qua loạt bài thuật toán sắp xếp để tìm hiểu nha. 

import java.util.Arrays;

public class Main {

    public static int maxSumTripleSorted(int[] arr, int n) {
        Arrays.sort(arr);
        return arr[n - 1] + arr[n - 2] + arr[n - 3];
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 7, 2, 10, 5};
        System.out.println(maxSumTripleSorted(arr, arr.length));
    }
}

Output: 22

Độ phức tạp: O(nlog(n))

Souce code: source

Link tham khảo: https://www.geeksforgeeks.org/maximum-triplet-sum-array/