Tổng tối đa sao cho không có hai phần tử nào là Phương thức thay thế liền kề trong chương trình C ++

Trong bài toán này, chúng ta đưa ra một mảng arr [] có kích thước n gồm các giá trị dương. Nhiệm vụ của chúng ta là tạo một chương trình để tìm dãy con tối đa theo cách sao cho không có hai phần tử liên tiếp của mảng.

Mô tả sự cố - Chúng ta cần tìm tổng của mảng con có các phần tử của mảng nhưng không xét đến hai phần tử liền kề của mảng.

Ví dụ

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

Đầu vào

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

Đầu ra

Giải thích -

Subarray sum are :
{5, 1, 6}, sum = 5 + 1 + 6 = 12
{2, 9}, sum = 2 + 9 = 11

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

Ở đây, chúng tôi sẽ có một giải pháp thay thế cho vấn đề đó là sử dụng cách tiếp cận lập trình adynamic. Trong cách tiếp cận này, chúng ta sẽ tìm các chuỗi đáp ứng điều kiện đã cho và in ra giá trị tối đa của nó. Phần tử maxSumDP [i] lưu trữ các dãy con sumof tối đa được tạo bằng cách lấy các phần tử từ chỉ số i đến n-1. Vì vậy, chúng ta có thể xem xét phần tử hiện tại của mảng arr [i] tức là maxSumDP [i] =arr [i] + maxSumDP [i + 2]. Hoặc không xem xét tốc độ hiện tại của mảng arr [i] tức là maxSumDP [i] =maxSumDP [i + 2].

Thuật toán

Khởi tạo -

maxSumDP[]

Bước 2 -

initialize the values of maxSumDP[n−1] and maxSumDP[n−2].
maxSumDP[n−1] = arr[n−1] and maxSumDP[n−2] = max(arr[n−1], arr[n−2]).

Bước 2 -

loop for i −> n−2 to 0

Bước 1.2 -

initialize the value of maxSumDP[i],
maxSumDP[i] = maximum of (arr[i] + maxSumDP[i + 2],
maxSumDP[i + 1])

Bước 3 -

Return maxSumDP[0] which is the maximum sum sequence sum.

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 calcMaxSum(int arr[], int n){
   int maxSumDP[n];
   maxSumDP[n−1] = arr[n−1];
   maxSumDP[n−2] = max(arr[n−1], arr[n−2]);
   for (int i = n − 2; i >= 0; i−−) {
      maxSumDP[i] = retMaxVal(arr[i] + maxSumDP[i + 2],
      maxSumDP[i + 1]);
   }
   return maxSumDP[0];
}
int main() {
   int arr[] = { 5, 2 , 1, 9, 6 };
   int n = sizeof(arr) / sizeof(int);
   cout<<"The maximum subsequence sum in such a way that no two consecutive elements of the array is "<<calcMaxSum(arr, n);
   return 0;
}

Đầu ra

The maximum subsequence sum in such a way that no two consecutive
elements of the array is 14