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

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

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

ที่นี่ เราต้องหาผลรวมของลำดับที่สร้างจากอาร์เรย์ โดยที่ไม่มีองค์ประกอบติดกันสามตัว

องค์ประกอบติดกัน (Consecutive elements) ของอาร์เรย์คือองค์ประกอบที่ทำตามลำดับดัชนีเดียวกัน

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

ตัวอย่าง

อินพุต

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

เอาต์พุต

32

คำอธิบาย

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

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

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

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

ค่าที่สามที่จะพิจารณาไม่สามารถพิจารณาโดยตรงได้ และสำหรับการพิจารณาผลรวม เราจะตรวจสอบเงื่อนไขกับสามค่าปัจจุบัน หากการพิจารณา 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], sum[i-1])

ตัวอย่างโค้ด

โปรแกรมแสดงการใช้งานวิธีแก้ปัญหาของเรา

#include <iostream> 
using namespace 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])); 
    for (int i = 3; i < n; i++){ 
        int sum1 = maxSumArr[i - 2] + arr[i]; 
        int sum2 = arr[i] + arr[i - 1] + maxSumArr[i - 3]; 
        maxSumArr[i] = max(max(maxSumArr[i - 1], sum1), sum2); 
    } 
    return maxSumArr[n - 1]; 
} 

int main() { 
    int arr[] = { 5, 9, 12, 15 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    cout << "The maximum subsequence sum such that no three are consecutive is " << findMaxSubSeqSum(arr, n); 
    return 0; 
}

เอาต์พุต

The maximum subsequence sum such that no three are consecutive is 32