Tổng lớn nhất trong mảng vòng sao cho không có hai phần tử liền kề trong C++

Trong bài toán này, chúng ta được cung cấp một mảng vòng cirArr[]. Nhiệm vụ là viết chương trình tìm tổng lớn nhất trong mảng vòng sao cho không có hai phần tử liền kề nhau được chọn trong C++.

Mô tả vấn đề

Đối với mảng vòng, ta cần tìm tổng lớn nhất của các phần tử sao cho không chọn hai phần tử liền kề, tức là phải chọn các phần tử xen kẽ nhau.

Mảng vòng là kiểu mảng đặc biệt mà phần tử cuối cùng được kết nối với phần tử đầu tiên.

Ví dụ minh họa:

Đầu vào

cirArr[] = {4, 1, 5, 3, 2}

Đầu ra

9

Giải thích

Dãy con vòng có tổng lớn nhất là [4, 5, 2]. Tổng = 9

Phương pháp giải

Giải pháp sử dụng quy hoạch động để tìm tổng lớn nhất. Ta xử lý mảng vòng bằng cách chia thành hai mảng con: một từ chỉ số 0 đến N-2 và một từ chỉ số 1 đến N-1. Tổng lớn nhất từ hai mảng này sẽ là kết quả.

Ví dụ chương trình

#include <iostream>
using namespace std;

int calcMaxVal(int a, int b) {
    if (a > b) return a;
    return b;
}

int calcMaxSumSubSeq(int cirArr[], int start, int end, int n) {
    int DP[n];
    int maxSum = 0;
    for (int i = start; i <= end; i++) {
        DP[i] = cirArr[i];
        if (maxSum < cirArr[i]) maxSum = cirArr[i];
    }
    for (int i = start + 2; i <= end; i++) {
        for (int j = 0; j < i - 1; j++) {
            if (DP[i] < DP[j] + cirArr[i]) {
                DP[i] = DP[j] + cirArr[i];
                if (maxSum < DP[i]) maxSum = DP[i];
            }
        }
    }
    return maxSum;
}

int findMaxSum(int cirArr[], int n) {
    int maxSumArray1 = calcMaxSumSubSeq(cirArr, 0, n-2, n);
    int maxSumArray2 = calcMaxSumSubSeq(cirArr, 1, n-1, n);
    return calcMaxVal(maxSumArray1, maxSumArray2);
}

int main() {
    int cirArr[] = {4, 1, 5, 3, 2};
    int n = sizeof(cirArr)/sizeof(cirArr[0]);
    cout << "Tổng lớn nhất trong mảng vòng không có phần tử liền kề: " << findMaxSum(cirArr, n);
    return 0;
}

Kết quả

Tổng lớn nhất trong mảng vòng không có phần tử liền kề: 9