Tổng đường đi lớn nhất tại mỗi vị trí với nhảy chia hết trong C++

Cho mảng n số. Từ vị trí i (1-based), có thể nhảy đến j nếu j chia hết cho i (j > i). Tìm tổng lớn nhất kết thúc tại mỗi vị trí.

Thuật toán (DP)

• dp[i]: tổng lớn nhất kết thúc tại i (0-based).
• Khởi tạo dp[i] = arr[i].
• Với mỗi i, duyệt ước số của i+1 (vì 1-based): j-1 và (i+1)/j - 1. Cập nhật max từ các dp đó.
• dp[i] += max_prev.

Ví dụ triển khai (C++)

#include <bits/stdc++.h>
using namespace std;

void printMaxSum(int arr[], int n) {
    int dp[n];
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < n; i++) {
        dp[i] = arr[i];
        int maxi = 0;
        for (int j = 1; j <= sqrt(i+1); j++) {
            if ((i+1) % j == 0 && (i+1) != j) {
                maxi = max(maxi, dp[j-1]);
                if (j != 1) maxi = max(maxi, dp[(i+1)/j - 1]);
            }
        }
        dp[i] += maxi;
    }
    for (int i = 0; i < n; i++) cout << dp[i] << " ";
}

int main() {
    int arr[] = {2, 3, 1, 4, 6, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    printMaxSum(arr, n);
    return 0;
}

Đầu ra

2 5 3 9 8 10