XNUMXつが連続しないような最大サブシーケンス合計


難易度 ミディアム
よく聞かれる 24 * 7イノベーションラボ アクセンチュア Amazon (アマゾン) デリーベリー PayPal PayU
配列 動的計画法

「XNUMXつが連続しないような最大サブシーケンス合計」という問題は、次のように与えられることを示しています。 配列 of 整数。 ここで、XNUMXつの連続する要素を考慮することができない場合、合計が最大になるサブシーケンスを見つける必要があります。 思い出してください。サブシーケンスは、元の入力配列からいくつかの要素が削除されたときに残される配列にすぎず、順序は同じです。

XNUMXつが連続しないような最大サブシーケンス合計

a[] = {2, 5, 10}
50

説明

これは5と10を選ぶのは簡単な選択でした。他の方法では合計が大きくなることはないからです。

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

説明

配列の中央にある5は選択しません。 それは、質問で課された条件を満たさないサブシーケンスを作成するためです。

アプローチ

この問題により、XNUMXつの連続する要素が選択されないように、合計が最大のサブシーケンスを見つけるように求められました。 したがって、単純なアプローチは、サブシーケンスの生成である可能性があります。 前の質問のいくつかで行ったように。 素朴なアプローチは、ほとんどの場合、サブシーケンスを生成し、サブシーケンスが質問で課せられた条件を満たすかどうかを確認することです。 しかし、このアプローチは時間がかかり、実際には使用できません。 中程度のサイズの入力でもこのアプローチを使用すると、制限時間を超えるためです。 したがって、問題を解決するには、他の方法を使用する必要があります。

我々は使用するだろう 動的計画法 問題を解決するために、しかしその前に、私たちはいくつかのケースワークを実行する必要があります。 このケースワークは、最初の問題をより小さなサブ問題に減らすために行われます。 動的計画法では、問題をより小さなサブ問題に還元するためです。 したがって、現在の要素をスキップすると、問題は前の要素まで問題を解決することになります。 現在の要素を選択することを検討してください。 次に、前の要素に対してXNUMXつの選択肢があります。 前の要素を選択するか、選択した場合、前の要素の前の要素を選択することはできません。 しかし、そうしないと、問題は前の要素の前まで問題を解決することになります。 コードを使用すると理解しやすくなります。

コード

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配列を作成する必要があったためです。 スペースの複雑さも線形です。