XNUMX 개가 연속되지 않는 최대 하위 시퀀스 합계

난이도 중급
자주 묻는 질문 24 * 7 Innovation Labs Accenture 아마존 배달 페이팔 알레그로
배열 동적 프로그래밍조회수 27
링크드 인버퍼레딧텀블러

"XNUMX 개가 연속되지 않는 최대 하위 시퀀스 합계"문제는 사용자에게 정렬 of 정수. 이제 세 개의 연속 요소를 고려할 수 없다는 점에서 최대 합이있는 하위 시퀀스를 찾아야합니다. 기억하자면, 하위 시퀀스는 순서를 동일하게 유지하면서 원래 입력 배열에서 일부 요소가 제거 될 때 남는 배열에 불과합니다.

예

XNUMX 개가 연속되지 않는 최대 하위 시퀀스 합계핀

a[] = {2, 5, 10}

50

설명

이것은 5와 10을 고르는 쉬운 선택이었습니다. 다른 방법은 더 큰 합계를 가져 오지 않기 때문입니다.

a[] = {5, 10, 5, 10, 15}
40

설명

배열 중간에있는 5 개는 선택하지 않습니다. 질문에 부과 된 조건을 만족하지 않는 하위 시퀀스가 ​​생성되기 때문입니다.

접근

문제는 세 개의 연속 요소가 선택되지 않도록 최대 합계가있는 하위 시퀀스를 찾도록 요청했습니다. 따라서 순진한 접근 방식은 하위 시퀀스의 생성이 될 수 있습니다. 이전 질문 중 일부에서했던 것처럼. 순진한 접근 방식은 대부분의 경우 하위 시퀀스를 생성 한 다음 하위 시퀀스가 ​​질문에 부과 된 조건을 충족하는지 확인하는 것입니다. 그러나이 방법은 시간이 많이 걸리고 실제로 사용할 수 없습니다. 중간 크기의 입력에도 접근 방식을 사용하면 시간 제한을 초과하기 때문입니다. 따라서 문제를 해결하려면 다른 방법을 사용해야합니다.

우리는 동적 프로그래밍 문제를 해결하려면 그 전에 몇 가지 케이스 워크를 수행해야합니다. 이 케이스 워크는 초기 문제를 더 작은 하위 문제로 줄이기 위해 수행됩니다. 동적 프로그래밍에서는 문제를 더 작은 하위 문제로 줄입니다. 따라서 현재 요소를 건너 뛰면 이전 요소까지 문제를 해결하는 것으로 축소됩니다. 현재 요소를 선택합니다. 그런 다음 이전 요소에 대해 두 가지 선택이 있습니다. 이전 요소를 선택하면 이전 요소보다 이전 요소를 선택할 수 없습니다. 그러나 그렇지 않으면 이전 요소 이전까지 문제를 해결하는 것으로 문제가 축소됩니다. 코드를 사용하면 더 쉽게 이해할 수 있습니다.

암호

XNUMX 개가 연속되지 않도록 최대 하위 시퀀스 합계를 찾는 C ++ 코드

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int a[] = {1, 2, 3, 4, 5, 6};
    int n = sizeof(a) / sizeof(a[0]);
    int dp[n];

    // base case
    if(n>=0)dp[0] = a[0];
    if(n>0)dp[1] = a[0] + a[1];
    if(n>1)dp[2] = max({a[0] + a[1], a[2]+a[0], a[2]+a[1]});
    // if you choose a[i], then choose a[i-1] that is dp[i] = a[i]+a[i-1]+dp[i-3]
    // if you choose a[i], then you do not choose a[i-1] dp[i] = dp[i-2] + a[i]
    // if you do not choose a[i], dp[i] = dp[i-1]
    for (int i = 3; i < n; i++)
        dp[i] = max({a[i]+a[i-1]+dp[i-3], dp[i-2]+a[i], dp[i-1]});
    cout<<dp[n-1];
}

16

XNUMX 개가 연속되지 않도록 최대 하위 시퀀스 합계를 찾는 Java 코드

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    int a[] = {1, 2, 3, 4, 5, 6};
    int n = a.length;
    int dp[] = new int[n];

    // base case
    if(n>=0)dp[0] = a[0];
    if(n>0)dp[1] = a[0] + a[1];
    if(n>1)dp[2] = Math.max(Math.max(a[0] + a[1], a[2]+a[0]), a[2]+a[1]);
    // if you choose a[i], then choose a[i-1] that is dp[i] = a[i]+a[i-1]+dp[i-3]
    // if you choose a[i], then you do not choose a[i-1] dp[i] = dp[i-2] + a[i]
    // if you do not choose a[i], dp[i] = dp[i-1]
    for (int i = 3; i < n; i++)
        dp[i] = Math.max(Math.max(a[i]+a[i-1]+dp[i-3], dp[i-2]+a[i]), dp[i-1]);

    System.out.println(dp[n-1]);
  }
}
16

복잡성 분석

시간 복잡성

의 위에), 우리는 단순히 어레이를 순회하고 DP 어레이를 계속 채웠기 때문입니다. 따라서 시간 복잡도는 선형입니다.

공간 복잡성

의 위에), 값을 저장하기 위해 XNUMX 차원 DP 배열을 만들어야했기 때문입니다. 공간 복잡성도 선형입니다.

링크드 인버퍼레딧텀블러
Translate »