Tổng số con tối đa sao cho không có ba con nào liên tiếp

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để tìm tổng số con tối đa sao cho không có ba nào liên tiếp nhau.

Đối với điều này, chúng tôi sẽ được cung cấp với một loạt các số nguyên dương. Nhiệm vụ của chúng ta là tìm tổng lớn nhất mà không lấy các số nguyên dương liên tiếp của chúng trong giá trị tổng.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
//returning maximum subsequence without involving
//three consecutive numbers
int maxSumWO3Consec(int arr[], int n) {
   int sum[n]; if (n >= 1) sum[0] = arr[0];
   if (n >= 2) sum[1] = arr[0] + arr[1];
   if (n > 2) sum[2] = max(sum[1], max(arr[1] + arr[2], arr[0] + arr[2]));
   for (int i = 3; i < n; i++)
      sum[i] = max(max(sum[i - 1], sum[i - 2] + arr[i]), arr[i] + arr[i - 1] + sum[i - 3]);
   return sum[n - 1];
}
int main() {
   int arr[] = { 100, 1000 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << maxSumWO3Consec(arr, n);
   return 0;
}

Đầu ra

1100