C++ 프로그램에서 3개가 연속되지 않는 최대 부분 시퀀스 합계

이 문제에서 n개의 양의 정수로 구성된 배열 arr[]가 주어집니다. 우리의 임무는 3개가 연속되지 않도록 최대 부분 수열 합을 찾는 프로그램을 만드는 것입니다.

문제 설명 − 여기서 연속된 세 개의 요소가 없도록 배열에서 생성된 시퀀스의 합을 찾아야 합니다.

연속적인 요소 배열은 동일한 인덱스 순서를 따르는 요소입니다.

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]

그러면 고려해야 할 세 번째 값은 직접 고려할 수 없습니다. 그리고 합계를 고려하여 현재 세 가지 조건을 확인합니다. 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 네임스페이스 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  
출력
 
3개가 연속되지 않는 최대 부분 수열 합은 32입니다.