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

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

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

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

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

อินพุต

rectGrid[2][] =389
411

ผลลัพธ์

13

คำอธิบาย

ผลรวมที่เป็นไปได้ทั้งหมดคือ

หากเราเริ่มจาก rectGrid[0][0] เช่น 3 เราก็เพิ่มได้เพียง 9 หรือ 1 ค่าสูงสุดคือ 12

หากเราเริ่มจาก rectGrid[1][0] เช่น 4 เราก็บวกได้เพียง 9 หรือ 1 ค่า maxSum คือ 13

หากเราเริ่มจาก rectGrid[0][1] เช่น 8 เราไม่สามารถเพิ่มองค์ประกอบใด ๆ ได้ ผลรวมสูงสุดคือ 8

หากเราเริ่มจาก rectGrid[1][1] เช่น 1 เราไม่สามารถเพิ่มองค์ประกอบใดๆ ได้ ผลรวมสูงสุดคือ 1

หากเราเริ่มจาก rectGrid[0][2] เช่น 9 เราก็บวกได้เพียง 3 หรือ 4 ค่าสูงสุดคือ 13

หากเราเริ่มจาก rectGrid[1][2] เช่น 1 เราก็บวกได้ 3 หรือ 4 เท่านั้น ผลรวมสูงสุดคือ 5

ยอดรวมสูงสุดคือ 13

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

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

ตัวอย่าง

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

#include<iostream>
using namespace std;
int findMax(int a, int b){
   if(a > b)
      return a;
      return b;
   }
int calcMaxSum(int rectGrid[2][20], int N){
   int currectSum = 0;
   int nextSum = 0;
   int altSum;
   for (int i = 0; i<N; i++ ){
      altSum = findMax(nextSum, currectSum);
      currectSum = nextSum + findMax(rectGrid[0][i], rectGrid[1][i]);
      nextSum = altSum;
   }
   int maxSum = findMax(nextSum, currectSum);
   return maxSum;
}
int main(){
   int rectGrid[2][20] = {{3, 8, 9, 5},
   {4, 1, 2, 7}};
   int N = 4;
   cout<<"The maximum sum in a 2 x "<<N<<" grid such that no two elements are adjacent is "<<calcMaxSum(rectGrid, N);
   return 0;
}

ผลลัพธ์

The maximum sum in a 2 x 4 grid such that no two elements are adjacent is 15