Tổng tối đa trong mảng tròn sao cho không có hai phần tử nào liền kề trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng tròn CirArr []. Nhiệm vụ của chúng ta là tạo một chương trình để tìm Tổng lớn nhất trong mảng tròn sao cho không có hai phần tử nào liền kề nhau trong C ++.

Mô tả vấn đề

Đối với mảng tròn, chúng ta cần tìm tổng tổng lớn nhất của các phần tử của mảng sao cho không thể lấy các phần tử liền kề, tức là chúng ta cần lấy các phần tử thay thế.

Mảng tròn là một kiểu mảng đặc biệt trong đó phần tử cuối cùng của mảng được kết nối với phần tử đầu tiên.

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

Đầu vào

cirArr[] = {4, 1, 5, 3, 2}

Đầu ra

9

Giải thích

Con của vòng tròn tổng lớn nhất là [4, 5, 2]. Tổng =9

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

Giải pháp cho vấn đề là sử dụng phương pháp lập trình động để tìm tổng lớn nhất. Tổng có thể được trích xuất bằng cách coi mảng tròn là hai mảng, một mảng từ chỉ số 0 đến N-2 và mảng khác từ chỉ số 1 đến n-1. Điều này sẽ tạo ra hai mảng và tổng lớn nhất của các tổng từ các mảng này sẽ là kết quả.

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 calcMaxVal(int a, int b){
   if(a > b)
      return a;
   return b;
}
int calcMaxSumSubSeq(int cirArr[], int start, int end, int n) {
   int DP[n];
   int maxSum = 0;
   for (int i = start; i < (end + 1); i++) {
      DP[i] = cirArr[i];
      if (maxSum < cirArr[i])
         maxSum = cirArr[i];
   }
   for (int i = (start + 2); i < (end + 1); i++) {
      for (int j = 0; j < i - 1; j++) {
         if (DP[i] < DP[j] + cirArr[i]) {
            DP[i] = DP[j] + cirArr[i];
            if (maxSum < DP[i])
               maxSum = DP[i];
         }
      }
   }
   return maxSum;
}
int findMaxSum(int cirArr[], int n){
   int maxSumArray1 = calcMaxSumSubSeq(cirArr, 0, (n-2), n);
   int maxSumArray2 = calcMaxSumSubSeq(cirArr, 1, (n-1), n);
   int maxSum = calcMaxVal(maxSumArray1, maxSumArray2);
   return maxSum;
}
int main(){
   int cirArr[] = {4, 1, 5, 3, 2};
   int n = sizeof(cirArr)/sizeof(cirArr[0]);
   cout<<"The maximum sum in circular array such that no two elements are adjacent is "<<findMaxSum(cirArr, n);
   return 0;
}

Đầu ra

The maximum sum in circular array such that no two elements are adjacent is 9