Tổng tối đa có thể cho một dãy con sao cho không có hai phần tử nào xuất hiện ở khoảng cách

Trong bài toán này, chúng ta cho một mảng arr [] có kích thước n và một số nguyên k. Ourtask là tạo một chương trình để tìm tổng lớn nhất có thể cho một chuỗi con mà không có hai phần tử nào xuất hiện ở khoảng cách

Mô tả sự cố - Chúng ta cần tìm tổng lớn nhất của sub-seqeunce có xét đến các phần tử cách nhau k.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

arr[] = {6, 2, 5, 1, 9, 11, 4} k = 2

Đầu ra

16

Giải thích

All possible sub−sequences of elements that differ by k or more.
{6, 1, 4}, sum = 11
{2, 9}, sum = 11
{5, 11}, sum = 16
{1, 4}, sum = 5
...
maxSum = 16

Phương pháp tiếp cận giải pháp

Một giải pháp cho vấn đề là sử dụng lập trình động. Đối với giải pháp, chúng tôi sẽ tìm tổng lớn nhất có thể cho đến phần tử hiện tại của mảng. Và lưu trữ nó vào DP [i], vì điều này, chúng ta sẽ tìm thấy tổng lớn nhất có thể. Đối với chỉ mục thứ i, chúng ta cần kiểm tra xem việc thêm giá trị chỉ số hiện tại có tăng lên tổng dãy con hay không.

if( DP[i − (k+1)] + arr[i] > DP[i − 1] )
−> DP[i] = DP[i − (k+1)] + arr[i]
otherwise DP[i] = DP[i−1]

Phần tử tối đa của mảng động cung cấp cho dãy con tối đa.

Thuật toán

Khởi tạo -

maxSumSubSeq = −1, maxSumDP[n]

Bước 1 -

Initialize maxSumDP[0] = arr[0]

Bước 2 -

Loop for i −> 1 to n.

Bước 2.1 -

if i < k −> maxSumDP[i] = maximum of arr[i] or
maxSumDP[i− 1].

Bước 2.2 -

else, maxSumDP[i] = maximum of arr[i] or maxSumDP[i − (k + 1)] + arr[i].

Bước 3 -

Find the maximum value of all elements from maxSumDP and store
it to maxSumSubSeq.

Bước 4 -

Return maxSumSubSeq

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

#include <iostream>
using namespace std;
int retMaxVal(int a, int b){
   if(a > b)
   return a;
   return b;
}
int calcMaxSumSubSeq(int arr[], int k, int n) {
   int maxSumDP[n];
   int maxSum = −1;
   maxSumDP[0] = arr[0];
   for (int i = 1; i < n; i++){
      if(i < k ){
         maxSumDP[i] = retMaxVal(arr[i], maxSumDP[i − 1]);
      }
      else
      maxSumDP[i] = retMaxVal(arr[i], maxSumDP[i − (k +
      1)] + arr[i]);
   }
   for(int i = 0; i < n; i++)
   maxSum = retMaxVal(maxSumDP[i], maxSum);
   return maxSum;
}
int main() {
   int arr[] = {6, 2, 5, 1, 9, 11, 4};
   int n = sizeof(arr) / sizeof(arr[0]);
   int k = 2;
   cout<<"The maximum sum possible for a sub−sequence such
   that no two elements appear at a distance < "<<k<<" in the array is "<<calcMaxSumSubSeq(arr, k, n);
   return 0;
}

Đầu ra

The maximum sum possible for a sub−sequence such that no two
elements appear at a distance < 2 in the array is 16