Максимальна сума підпослідовностей, така що не три послідовні


Рівень складності Medium
Часто запитують у 24 * 7 Інноваційні лабораторії Accenture Амазонка Делівері PayPal PayU
масив Динамічне програмування

У задачі “Максимальна сума підпорядкованості, така що не існує трьох послідовних” вказується, що вам дано масив of цілих чисел. Тепер вам потрібно знайти підпослідовність, яка має максимальну суму, враховуючи те, що ви не можете розглянути три послідовні елементи. Нагадаємо, підпослідовність - це не що інше, як масив, який залишається, коли деякі елементи видаляються з вихідного масиву вводу, зберігаючи порядок незмінним.

Приклад

Максимальна сума підпослідовностей, така що не три послідовні

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

Пояснення

Це був простий вибір, щоб вибрати 5 і 10. Оскільки будь-який інший спосіб не призведе до більшої суми.

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

Пояснення

Ми не вибираємо 5, що знаходиться в середині масиву. Тому що це створить підпослідовність, яка не задовольняє умові, накладеній у питанні.

Підхід

Проблема попросила нас знайти підпослідовність з максимальною сумою, такою, щоб не було вибрано три послідовні елементи. Таким чином, наївним підходом може бути породження послідовностей. Як ми це робили в деяких попередніх питаннях. Наївний підхід - це більшу частину часу, щоб генерувати підпослідовності, а потім перевіряти, чи відповідає підпослідовність умовам, які висуваються у питанні. Але такий підхід трудомісткий і практично не може бути використаний. Оскільки використання підходу навіть для вхідних даних середнього розміру перевищує обмеження часу. Таким чином, для вирішення проблеми нам потрібно використовувати інший метод.

Ми будемо використовувати Динамічне програмування щоб вирішити проблему, але перед цим нам потрібно виконати певну роботу. Ця робота виконується для зменшення початкової проблеми на менші підзадачі. Оскільки при динамічному програмуванні ми зводимо проблему до менших підзадач. Отже, розглянемо, як ми пропускаємо поточний елемент, тоді наша проблема зводиться до вирішення проблеми до попереднього елемента. Поміркуйте, ми вибираємо поточний елемент. Тоді ми маємо два варіанти попереднього елемента. Або ми обираємо попередній елемент, якщо ж це робимо, то ми не можемо вибрати елемент, що передував попередньому елементу. Але якщо ми цього не зробимо, проблема зводиться до вирішення проблеми до попереднього до попереднього елемента. Це буде легше зрозуміти, використовуючи код.

код

Код С ++ для знаходження максимальної суми підпослідовності такої, щоб не було трьох послідовних

#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

Код 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

Аналіз складності

Складність часу

O (N), тому що ми просто обходили масив і продовжували заповнювати наш масив DP. Таким чином, часова складність є лінійною.

Складність простору

O (N), оскільки нам потрібно було створити одновимірний масив DP для зберігання значень. Складність простору також лінійна.