home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Maximum sum subsequence with at-least k distant elements in C++

ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมหาผลรวมสูงสุดของลำดับย่อย (subsequence) ที่แต่ละองค์ประกอบห่างกันอย่างน้อย k ตำแหน่ง

เราจะได้รับอาร์เรย์จำนวนเต็มและค่า K งานคือหาลำดับย่อยที่มีผลรวมสูงสุด โดยที่ทุกคู่ขององค์ประกอบในลำดับย่อยต้องห่างกันอย่างน้อย K ตำแหน่ง

ตัวอย่างโค้ด

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

int maxSum(int arr[], int N, int k) {
    int MS[N];
    MS[N - 1] = arr[N - 1];
    for (int i = N - 2; i >= 0; i--) {
        if (i + k + 1 >= N)
            MS[i] = max(arr[i], MS[i + 1]);
        else
            MS[i] = max(arr[i] + MS[i + k + 1], MS[i + 1]);
    }
    return MS[0];
}

int main() {
    int N = 10, k = 2;
    int arr[] = {50, 70, 40, 50, 90, 70, 60, 40, 70, 50};
    cout << maxSum(arr, N, k);
    return 0;
}

เอาต์พุต

230