ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ขนาด n ซึ่งประกอบด้วยค่าบวก หน้าที่ของเราคือสร้างโปรแกรมเพื่อค้นหาผลรวมสูงสุดในลักษณะที่ไม่มีองค์ประกอบที่ต่อเนื่องกันสององค์ประกอบในอาร์เรย์
คำอธิบายปัญหา − เราจำเป็นต้องหาผลรวมของ subarray ที่มีองค์ประกอบของอาร์เรย์ แต่ไม่มีองค์ประกอบที่อยู่ติดกัน 2 ตัวของอาร์เรย์ที่นำมาพิจารณา
ตัวอย่าง
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
arr[] = {5, 2, 1, 9, 6} ผลลัพธ์
คำอธิบาย −
Subarray sum are :
{5, 1, 6}, sum = 5 + 1 + 6 = 12
{2, 9}, sum = 2 + 9 = 11 แนวทางการแก้ปัญหา
ในที่นี้ เราจะมีวิธีแก้ปัญหาแบบอื่นที่ใช้แนวทางการเขียนโปรแกรมแบบอะไดนามิก ในแนวทางนี้ เราจะพบผลลัพธ์ที่ตามมาซึ่งเป็นไปตามเงื่อนไขที่กำหนดและพิมพ์ค่าสูงสุดของเงื่อนไขนั้น เราจะสร้างอาร์เรย์ maxSumDP[n] ที่เก็บค่าย่อยสูงสุดของลำดับย่อยที่สร้างขึ้น องค์ประกอบ maxSumDP[i] เก็บผลรวมสูงสุดของลำดับย่อยที่สร้างขึ้นโดยการนำองค์ประกอบจากดัชนี i ถึง n-1 สำหรับสิ่งนี้ เราสามารถพิจารณาองค์ประกอบปัจจุบันของอาร์เรย์ arr[i] i.e.maxSumDP[i] =arr[i] + maxSumDP[i+2] หรือไม่พิจารณาองค์ประกอบปัจจุบันของอาร์เรย์ arr[i] เช่น maxSumDP[i] =maxSumDP[i+2]
อัลกอริทึม
เริ่มต้น −
maxSumDP[]
ขั้นตอนที่ 2 −
initialize the values of maxSumDP[n−1] and maxSumDP[n−2]. maxSumDP[n−1] = arr[n−1] and maxSumDP[n−2] = max(arr[n−1], arr[n−2]).
ขั้นตอนที่ 2 −
loop for i −> n−2 to 0
ขั้นตอนที่ 1.2 −
initialize the value of maxSumDP[i], maxSumDP[i] = maximum of (arr[i] + maxSumDP[i + 2], maxSumDP[i + 1])
ขั้นตอนที่ 3 −
Return maxSumDP[0] which is the maximum sum sequence sum.
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <iostream>
using namespace std;
int retMaxVal(int a, int b){
if(a > b)
return a;
return b;
}
int calcMaxSum(int arr[], int n){
int maxSumDP[n];
maxSumDP[n−1] = arr[n−1];
maxSumDP[n−2] = max(arr[n−1], arr[n−2]);
for (int i = n − 2; i >= 0; i−−) {
maxSumDP[i] = retMaxVal(arr[i] + maxSumDP[i + 2],
maxSumDP[i + 1]);
}
return maxSumDP[0];
}
int main() {
int arr[] = { 5, 2 , 1, 9, 6 };
int n = sizeof(arr) / sizeof(int);
cout<<"The maximum subsequence sum in such a way that no two consecutive elements of the array is "<<calcMaxSum(arr, n);
return 0;
} ผลลัพธ์
The maximum subsequence sum in such a way that no two consecutive elements of the array is 14
