ผลรวมสูงสุดในอาร์เรย์แบบวงกลมที่ไม่มีองค์ประกอบสองตัวอยู่ติดกันใน C ++

ในปัญหานี้ เราได้รับอาร์เรย์แบบวงกลม cirArr[] งานของเราคือสร้างโปรแกรมเพื่อค้นหาผลรวมสูงสุดในอาร์เรย์แบบวงกลมเพื่อไม่ให้มีองค์ประกอบสองรายการอยู่ติดกันใน C ++

คำอธิบายปัญหา

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

อาร์เรย์แบบวงกลม เป็นอาร์เรย์ชนิดพิเศษที่องค์ประกอบสุดท้ายของอาร์เรย์เชื่อมต่อกับองค์ประกอบแรก

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

อินพุต

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

ผลลัพธ์

9

คำอธิบาย

ผลรวมของลำดับรองแบบวงกลมสูงสุดคือ [4, 5, 2] ผลรวม =9

แนวทางการแก้ปัญหา

วิธีแก้ปัญหาคือใช้วิธีการเขียนโปรแกรมแบบไดนามิกเพื่อค้นหาผลรวมสูงสุด ผลรวมสามารถแยกออกมาได้โดยถือว่าอาร์เรย์วงกลมเป็นอาร์เรย์สองอาร์เรย์ อาร์เรย์หนึ่งจากดัชนี 0 ถึง N-2 และอีกรายการหนึ่งจากดัชนี 1 ถึง n-1 สิ่งนี้จะสร้างสองอาร์เรย์และผลรวมสูงสุดของผลรวมจากอาร์เรย์เหล่านี้จะเป็นผล

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#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;
}

ผลลัพธ์

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