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

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ที่ประกอบด้วยจำนวนเต็มบวก n ตัว หน้าที่ของเราคือสร้างโปรแกรมเพื่อค้นหาผลรวมสูงสุดของลำดับซึ่งไม่มีสามอันที่ต่อเนื่องกัน

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

องค์ประกอบต่อเนื่องของ อาร์เรย์คือองค์ประกอบที่เป็นไปตามลำดับของดัชนีเดียวกัน

arr[0], arr[1], arr[2], …

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

อินพุต

arr[] ={5, 9, 12, 15}

ผลลัพธ์

32

คำอธิบาย

ผลรวม =5 + 12 + 15 =32

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

วิธีแก้ปัญหาอย่างง่ายคือการสร้างอาร์เรย์เสริมเพื่อเก็บผลรวมจนถึงดัชนีปัจจุบัน แล้วหาผลรวมและตรวจสอบผลรวมจนถึงดัชนีโดยการตรวจสอบหาผลรวมต่อเนื่อง

สำหรับค่าผลรวมสองค่าแรก sumVal[0] =arr[0]sumVal[1] =arr[0] + arr[1]

แล้วค่าที่ 3 ที่จะนำมาพิจารณานั้นไม่สามารถพิจารณาได้โดยตรง และพิจารณาผลรวม เราจะตรวจสอบเงื่อนไขกับสามปัจจุบัน ถ้าพิจารณา arr[i] ให้เพิ่มค่ารวม ไม่รวม arr[i−1] หรือ arr[i−2] ไม่เช่นนั้น ให้ถือว่า arr[i ] ผลรวมยังคงเท่าเดิม

sum[i] =max(sum[i−3] + arr[i−1] + arr[i], sum[i−2] + arr[i], ผลรวม[i−1]) 
ตัวอย่าง
 

 โปรแกรมแสดงการใช้งานโซลูชันของเรา 
 
#include ใช้เนมสเปซ std;int findMaxSubSeqSum(int arr[], int n) { int maxSumArr[n]; maxSumArr[0] =arr[0]; maxSumArr[1] =arr[0] + arr[1]; maxSumArr[2] =max(maxSumArr[1], max(arr[1] + arr[2], arr[0] + arr[2])); สำหรับ (int i =3; i  
ผลลัพธ์
 
ผลรวมลำดับสูงสุดที่ไม่มีลำดับที่สามคือ 32