Tổng lớn nhất không có hai phần tử liền kề trong C++

Cho mảng arr[]. Tìm tổng lớn nhất của dãy con không có 2 phần tử liền kề.

Ví dụ

Đầu vào: arr[] = {5, 1, 3, 7, 9, 2, 5}

Đầu ra: 22

Giải thích

Từ chỉ số 0 cách nhau: 5 + 3 + 9 + 5 = 22
Từ chỉ số 1 cách nhau: 1 + 7 + 2 = 10

Phương pháp giải

Duyệt mảng, giữ hai biến tổng: maxSum1 (có phần tử hiện tại) và maxSum2 (không có phần tử hiện tại). Mỗi vòng cập nhật maxSum2 = max(maxSum1, maxSum2), sau đó maxSum1 = maxSum2_old + arr[i]. Cuối cùng max của hai biến là kết quả.

Ví dụ

#include <iostream>
using namespace std;

int findmaximum(int a, int b) {
    return (a > b) ? a : b;
}

int findMaxSumWOAdjecent(int arr[], int N) {
    int maxSum1 = arr[0];
    int maxSum2 = 0;
    int temp;
    for (int i = 1; i < N; i++) {
        temp = findmaximum(maxSum1, maxSum2);
        maxSum1 = maxSum2 + arr[i];
        maxSum2 = temp;
    }
    return findmaximum(maxSum1, maxSum2);
}

int main() {
    int arr[] = {5, 1, 3, 7, 9, 2, 5};
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << "Tổng lớn nhất không có 2 phần tử liền kề: " << findMaxSumWOAdjecent(arr, N);
    return 0;
}

Đầu ra

Tổng lớn nhất không có 2 phần tử liền kề: 22