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

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

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

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

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

อินพุต

arr[] = {5, 1, 3, 7, 9, 2, 5}

ผลลัพธ์

22

คำอธิบาย

Taking sum sequence from index 0 with alternate elements : 5 + 3 + 9 + 5 = 22
Taking sum sequence from index 1 with alternate elements : 1 + 7 + 2 = 10

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

ในการแก้ปัญหา เราจะวนรอบองค์ประกอบทั้งหมดของอาร์เรย์และรักษาผลรวมไว้สองจำนวน sumVar1 และ sumVar2 sumVar1 จะรวมผลรวมกับองค์ประกอบปัจจุบัน และ sumVar2 จะรวมผลรวมที่ไม่มีองค์ประกอบปัจจุบัน

ทุกครั้งที่ทำซ้ำ เราจะอัปเดต sumVar2 เป็น max(sumVar1, sumVar2) จากนั้นอัปเดต sumVar1 เมื่อสิ้นสุดลูป sumVar2 จะให้ผลรวมที่ต้องการ

ตัวอย่าง

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

#include<iostream>
using namespace std;
int findmaximum(int a, int b){
   if(a > b)
      return a;
      return b;
}
int findMaxSumWOAdjecent(int arr[], int N){
   int maxSum1 = arr[0];
   int maxSum2 = 0;
   int temp;
   for (int i = 1; i < N; i++) {
      temp = findmaximum(maxSum1, maxSum2);
      maxSum1 = maxSum2 + arr[i];
      maxSum2 = temp;
   }
   return (findmaximum(maxSum1, maxSum2));
}
int main(){
   int arr[] = {5, 1, 3, 7, 9, 2, 5};
   int N = sizeof(arr) / sizeof(arr[0]);
   cout<<"The maximum sum such that no two elements are adjacent is "<<findMaxSumWOAdjecent(arr, N);
   return 0;
}

ผลลัพธ์

The maximum sum such that no two elements are adjacent is 22