ในปัญหานี้ เราได้รับอาร์เรย์ 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
แนวทางการแก้ปัญหา
ในเซตที่แล้ว เราได้เห็นแนวทางหนึ่งในการแก้ปัญหานี้แล้ว ที่นี่ เราจะเรียนรู้เกี่ยวกับวิธีการเขียนโปรแกรมแบบไดนามิกเพื่อแก้ปัญหา
ในการแก้ปัญหาโดยใช้ Dynamic Approach เราจำเป็นต้องสร้างอาร์เรย์ DP[] ที่จัดเก็บผลรวมสูงสุดจนถึงดัชนีปัจจุบัน แล้วหาดัชนีผลรวมโดยใช้อาร์เรย์ไดนามิกนี้
DP max ปัจจุบันคือค่าสูงสุดของ dp[i+2]+ arr[i] และ dp[i+1]
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <iostream>
using namespace std;
int DP[100];
bool currState[100];
int maxVal(int a, int b){
if(a > b)
return a;
return b;
}
int calcMaxSumWOAdj(int arr[], int i, int n){
if (i >= n)
return 0;
if (currState[i])
return DP[i];
currState[i] = 1;
DP[i] = maxVal(calcMaxSumWOAdj(arr, i + 1, n), arr[i] + calcMaxSumWOAdj(arr, i + 2, n));
return DP[i];
}
int main(){
int arr[] = { 5, 1, 3, 7, 9, 2, 5 };
int n = sizeof(arr) / sizeof(int);
cout<<"The maximum sum such that no two elements are adjacent is "<<calcMaxSumWOAdj(arr, 0, n);
return 0;
} ผลลัพธ์
The maximum sum such that no two elements are adjacent is 22
