Рубрики

Максимальная сумма подпоследовательности, при которой три не являются последовательными

Учитывая последовательность положительных чисел, найдите максимальную сумму, которая может быть сформирована без трех последовательных элементов.

Примеры :

Input: arr[] = {1, 2, 3}
Output: 5
We can't take three of them, so answer is
2 + 3 = 5

Input: arr[] = {3000, 2000, 1000, 3, 10}
Output: 5013 
3000 + 2000 + 3 + 10 = 5013

Input: arr[] = {100, 1000, 100, 1000, 1}
Output: 2101
100 + 1000 + 1000 + 1 = 2101

Input: arr[] = {1, 1, 1, 1, 1}
Output: 4

Input: arr[] = {1, 2, 3, 4, 5, 6, 7, 8}
Output: 27

Эта проблема в основном является расширением нижеприведенной проблемы.

Максимальная сумма, при которой нет двух соседних элементов

Мы поддерживаем вспомогательный массив sum [] (того же размера, что и входной массив), чтобы найти результат.

sum[i] : Stores result for subarray arr[0..i], i.e.,
         maximum possible sum in subarray arr[0..i]
         such that no three elements are consecutive.

sum[0] = arr[0]

// Note : All elements are positive
sum[1] = arr[0] + arr[1]

// We have three cases
// 1) Exclude arr[2], i.e., sum[2] = sum[1]
// 2) Exclude arr[1], i.e., sum[2] = sum[0] + arr[2]
// 3) Exclude arr[0], i.e., sum[2] = arr[1] + arr[2] 
sum[2] = max(sum[1], arr[0] + arr[2], arr[1] + arr[2])

In general,
// We have three cases
// 1) Exclude arr[i],  i.e.,  sum[i] = sum[i-1]
// 2) Exclude arr[i-1], i.e., sum[i] = sum[i-2] + arr[i]
// 3) Exclude arr[i-2], i.e., sum[i-3] + arr[i] + arr[i-1] 
sum[i] = max(sum[i-1], sum[i-2] + arr[i],
             sum[i-3] + arr[i] + arr[i-1])

Ниже приведена реализация вышеуказанной идеи.

C / C ++

// C ++ программа для поиска максимальной суммы такой, что
// нет трех последовательных
#include <bits/stdc++.h>

using namespace std;

  
// Возвращает максимальную сумму подпоследовательности, так что нет трех
// элементы являются последовательными

int maxSumWO3Consec(int arr[], int n)

{

    // Сохраняет результат для подмассива arr [0..i], т.е.

    // максимально возможная сумма в подмассиве arr [0..i]

    // такой, что никакие три элемента не являются последовательными.

    int sum[n];

  

    // Базовые случаи (обработать первые три элемента)

    if (n >= 1)

        sum[0] = arr[0];

  

    if (n >= 2)

        sum[1] = arr[0] + arr[1];

  

    if (n > 2)

        sum[2] = max(sum[1], max(arr[1] + arr[2], arr[0] + arr[2]));

  

    // Обработка остальных элементов

    // У нас есть три случая

    // 1) Исключить arr [i], т.е. sum [i] = sum [i-1]

    // 2) Исключить arr [i-1], то есть sum [i] = sum [i-2] + arr [i]

    // 3) Исключить arr [i-2], т. Е. Sum [i-3] + arr [i] + arr [i-1]

    for (int i = 3; i < n; i++)

        sum[i] = max(max(sum[i - 1], sum[i - 2] + arr[i]),

                     arr[i] + arr[i - 1] + sum[i - 3]);

  

    return sum[n - 1];

}

  
// Код драйвера

int main()

{

    int arr[] = { 100, 1000 };

    int n = sizeof(arr) / sizeof(arr[0]);

    cout << maxSumWO3Consec(arr, n);

    return 0;

}

Джава

// Java-программа для поиска максимальной суммы
// так, что нет трех последовательных

import java.io.*;

  

class GFG {

  

    // Возвращает максимальную сумму подпоследовательности, так что нет трех

    // элементы являются последовательными

    static int maxSumWO3Consec(int arr[], int n)

    {

        // Сохраняет результат для подмассива arr [0..i], т.е.

        // максимально возможная сумма в подмассиве arr [0..i]

        // такой, что никакие три элемента не являются последовательными.

        int sum[] = new int[n];

  

        // Базовые случаи (обработать первые три элемента)

        if (n >= 1)

            sum[0] = arr[0];

  

        if (n >= 2)

            sum[1] = arr[0] + arr[1];

  

        if (n > 2)

            sum[2] = Math.max(sum[1], Math.max(arr[1] + arr[2], arr[0] + arr[2]));

  

        // Обработка остальных элементов

        // У нас есть три случая

        // 1) Исключить arr [i], т.е. sum [i] = sum [i-1]

        // 2) Исключить arr [i-1], то есть sum [i] = sum [i-2] + arr [i]

        // 3) Исключить arr [i-2], т. Е. Sum [i-3] + arr [i] + arr [i-1]

        for (int i = 3; i < n; i++)

            sum[i] = Math.max(Math.max(sum[i - 1], sum[i - 2] + arr[i]),

                              arr[i] + arr[i - 1] + sum[i - 3]);

  

        return sum[n - 1];

    }

  

    // Код драйвера

    public static void main(String[] args)

    {

        int arr[] = { 100, 1000, 100, 1000, 1 };

        int n = arr.length;

        System.out.println(maxSumWO3Consec(arr, n));

    }

}

  
// Этот код предоставлен vt_m

питон

# Программа Python для поиска максимальной суммы такой, что
№ три не являются последовательными

  
# Возвращает максимальную сумму подпоследовательности, такую, что нет трех
# элементы являются последовательными

def maxSumWO3Consec(arr, n):

    # Сохраняет результат для подмассива arr [0..i], т.е.

    # максимально возможная сумма в подмассивном массиве [0..i]

    # такое, что никакие три элемента не являются последовательными.

    sum = [0 for k in range(n)]

  

    # Базовые случаи (обработать первые три элемента)

      

    if n >= 1 :

        sum[0] = arr[0]

      

    if n >= 2 :

        sum[1] = arr[0] + arr[1]

      

    if n > 2 :

        sum[2] = max(sum[1], max(arr[1] + arr[2], arr[0] + arr[2]))

  

    # Обработка остальных элементов

    # У нас есть три случая

    # 1) Исключить arr [i], то есть sum [i] = sum [i-1]

    # 2) Исключить arr [i-1], т. Е. Sum [i] = sum [i-2] + arr [i]

    # 3) Исключить arr [i-2], т. Е. Sum [i-3] + arr [i] + arr [i-1]

    for i in range(3, n):

        sum[i] = max(max(sum[i-1], sum[i-2] + arr[i]), arr[i] + arr[i-1] + sum[i-3])

  

    return sum[n-1]

  
# Код драйвера

arr = [100, 1000, 100, 1000, 1]

n = len(arr)

print maxSumWO3Consec(arr, n)

  
# Этот код предоставлен Афзалом Ансари

C #

// C # программа для поиска максимальной суммы
// так, что нет трех последовательных

using System;

class GFG {

  

    // Возвращает максимальную подпоследовательность

    // сумма такая, что нет трех

    // элементы являются последовательными

    static int maxSumWO3Consec(int[] arr,

                               int n)

    {

        // Сохраняет результат для подмассива

        // arr [0..i], т.е. максимум

        // возможная сумма в подмассиве

        // arr [0..i] такой, что нет

        // три элемента являются последовательными.

        int[] sum = new int[n];

  

        // Базовые случаи (процесс

        // первые три элемента)

        if (n >= 1)

            sum[0] = arr[0];

  

        if (n >= 2)

            sum[1] = arr[0] + arr[1];

  

        if (n > 2)

            sum[2] = Math.Max(sum[1], Math.Max(arr[1] + arr[2], arr[0] + arr[2]));

  

        // Обработка остальных элементов

        // У нас есть три случая

        // 1) Исключить arr [i], т.е.

        // sum [i] = sum [i-1]

        // 2) Исключить arr [i-1], т.е.

        // sum [i] = sum [i-2] + arr [i]

        // 3) Исключить arr [i-2], т.е.

        // сумма [i-3] + arr [i] + arr [i-1]

        for (int i = 3; i < n; i++)

            sum[i] = Math.Max(Math.Max(sum[i - 1],

                                       sum[i - 2] + arr[i]),

                              arr[i] + arr[i - 1] + sum[i - 3]);

  

        return sum[n - 1];

    }

  

    // Код драйвера

    public static void Main()

    {

        int[] arr = { 100, 1000, 100, 1000, 1 };

        int n = arr.Length;

        Console.Write(maxSumWO3Consec(arr, n));

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// PHP программа для поиска максимума
// сумма такая, что нет трех последовательных

  
// Возвращает максимальную подпоследовательность
// сумма такая, что нет трех
// элементы являются последовательными

function maxSumWO3Consec($arr, $n)

{

    // Сохраняет результат для подмассива

    // arr [0..i], т.е. максимум

    // возможная сумма в подмассиве

    // arr [0..i] такой, что нет трех

    // элементы являются последовательными $.

    $sum = array();

  

    // Базовые случаи (процесс

    // первые три элемента)

    if ( $n >= 1)

    $sum[0] = $arr[0];

      

    if ($n >= 2)

    $sum[1] = $arr[0] + $arr[1];

      

    if ( $n > 2)

    $sum[2] = max($sum[1], max($arr[1] + $arr[2], 

                            $arr[0] + $arr[2]));

  

    // Обработка остальных элементов

    // У нас есть три случая

    // 1) Исключить arr [i], т.е.

    // sum [i] = sum [i-1]

    // 2) Исключить arr [i-1], т.е.

    // sum [i] = sum [i-2] + arr [i]

    // 3) Исключить arr [i-2], т.е.

    // сумма [i-3] + arr [i] + arr [i-1]

    for ($i = 3; $i < $n; $i++)

        $sum[$i] = max(max($sum[$i - 1], 

                        $sum[$i - 2] + $arr[$i]), 

                        $arr[$i] + $arr[$i - 1] + 

                                    $sum[$i - 3]);

  

    return $sum[$n-1];

}

  
// Код драйвера

$arr = array(100, 1000, 100, 1000, 1);

$n =count($arr);

echo maxSumWO3Consec($arr, $n);

  
// Этот код предоставлен anuj_67.
?>

Выход :

2101

Сложность времени: O (n)
Вспомогательное пространство: O (n)

Другой подход: (с использованием рекурсии)

C ++

// C ++ программа для поиска максимальной суммы такой, что
// нет трех последовательных, использующих рекурсию.
#include<bits/stdc++.h>

using namespace std;

  

int arr[] = {100, 1000, 100, 1000, 1};

int sum[10000];

  
// Возвращает максимальную сумму подпоследовательности, так что нет трех
// элементы являются последовательными

int maxSumWO3Consec(int n)

{

    if(sum[n]!=-1)

    return sum[n];

      

    // Базовые случаи (обработать первые три элемента)

      

    if(n==0)

    return sum[n] = 0;

      

    if(n==1)

    return sum[n] = arr[0];

      

    if(n==2)

    return sum[n] = arr[1]+arr[0];

      

    // Обработка остальных элементов

    // У нас есть три случая

    return sum[n] = max(max(maxSumWO3Consec(n-1),

                    maxSumWO3Consec(n-2) + arr[n-1]), 

                    arr[n-2] + arr[n-1] + maxSumWO3Consec(n-3));

      

      
}

  
// Код драйвера

int main()

{

      

    int n = sizeof(arr) / sizeof(arr[0]);

    memset(sum,-1,sizeof(sum));

    cout << maxSumWO3Consec(n); 

  
// этот код предоставлен Kushdeep Mittal

    return 0; 

}

Джава

// Java программа для поиска максимума
// сумма такая, что нет трех
// последовательное использование рекурсии.

import java.util.Arrays;

  

class GFG 

{

      

static int arr[] = {100, 1000, 100, 1000, 1}; 

static int sum[] = new int[10000]; 

  
// Возвращает максимальную подпоследовательность
// сумма такая, что нет трех
// элементы являются последовательными

static int maxSumWO3Consec(int n) 

    if(sum[n] != -1

        return sum[n]; 

      

    // Базовые случаи (обработать первые три элемента)

      

    if(n == 0

        return sum[n] = 0

      

    if(n == 1

        return sum[n] = arr[0]; 

      

    if(n == 2

        return sum[n] = arr[1] + arr[0]; 

      

    // Обработка остальных элементов

    // У нас есть три случая

    return sum[n] = Math.max(Math.max(maxSumWO3Consec(n - 1), 

                    maxSumWO3Consec(n - 2) + arr[n - 1]), 

                    arr[n - 2] + arr[n - 1] + maxSumWO3Consec(n - 3)); 

      

      

  
// Код драйвера

public static void main(String[] args) 

{

    int n = arr.length; 

        Arrays.fill(sum, -1);

    System.out.println(maxSumWO3Consec(n));

}
}

  
// Этот код предоставлен Rajput-Ji

python3

# Python3 программа для поиска максимума
# сумма такая, что нет трех последовательных
# используя рекурсию.

arr = [100, 1000, 100, 1000, 1]

sum = [-1] * 10000

  
# Возвращает максимальную сумму подпоследовательности, такую
# что никакие три элемента не являются последовательными

def maxSumWO3Consec(n) :

  

    if(sum[n] != -1):

        return sum[n]

      

    # 3 Базовые случаи (процесс первый

    # три элемента)

    if(n == 0) : 

        sum[n] = 0

        return sum[n]

      

    if(n == 1) : 

        sum[n] = arr[0]

        return sum[n]

      

    if(n == 2) : 

        sum[n] = arr[1] + arr[0

        return sum[n]

      

    # Обработка остальных элементов

    # У нас есть три случая

    sum[n] = max(max(maxSumWO3Consec(n - 1), 

                     maxSumWO3Consec(n - 2) + arr[n - 1]), 

                     arr[n - 2] + arr[n - 1] + 

                     maxSumWO3Consec(n - 3))

      

    return sum[n]

  
# Код драйвера

if __name__ == "__main__" :

  

    n = len(arr)

      

    print(maxSumWO3Consec(n))

  
# Этот код предоставлен Ryuga

C #

// C # программа для поиска максимума
// сумма такая, что нет трех
// последовательное использование рекурсии.

using System;

  

class GFG 

  

    static int []arr = {100, 1000,

                        100, 1000, 1}; 

    static int []sum = new int[10000]; 

  

    // Возвращает максимальную подпоследовательность

    // сумма такая, что нет трех

    // элементы являются последовательными

    static int maxSumWO3Consec(int n) 

    

        if(sum[n] != -1) 

            return sum[n]; 

  

        // Базовые случаи (сначала обработать

        // три элемента)

        if(n == 0) 

            return sum[n] = 0; 

  

        if(n == 1) 

            return sum[n] = arr[0]; 

  

        if(n == 2) 

            return sum[n] = arr[1] + arr[0]; 

  

        // Обработка остальных элементов

        // У нас есть три случая

        return sum[n] = Math.Max(Math.Max(maxSumWO3Consec(n - 1), 

                        maxSumWO3Consec(n - 2) + arr[n - 1]), 

                        arr[n - 2] + arr[n - 1] + maxSumWO3Consec(n - 3)); 

  

  

    

  

    // Код драйвера

    public static void Main(String[] args) 

    

        int n = arr.Length; 

        for(int i = 0; i < sum.Length; i++)

            sum[i] = -1;

        Console.WriteLine(maxSumWO3Consec(n)); 

    

}

  
// Этот код предоставлен 29AjayKumar

PHP

<?php
// PHP программа для нахождения максимальной суммы такой, что
// нет трех последовательных, использующих рекурсию.

$arr = array(100, 1000, 100, 1000, 1);

$sum = array_fill(0, count($arr) + 1, -1);

  
// Возвращает максимальную сумму подпоследовательности, такую что
// нет трех элементов подряд

function maxSumWO3Consec($n)

{

    global $sum,$arr;

    if($sum[$n] != -1)

        return $sum[$n];

      

    // Базовые случаи (обработать первые три элемента)

    if($n == 0)

        return $sum[$n] = 0;

      

    if($n == 1)

        return $sum[$n] = $arr[0];

      

    if($n == 2)

        return $sum[$n] = $arr[1] + $arr[0];

      

    // Обработка остальных элементов

    // У нас есть три случая

    return $sum[$n] = max(max(maxSumWO3Consec($n - 1),

                              maxSumWO3Consec($n - 2) + $arr[$n - 1]), 

                                              $arr[$n - 2] + $arr[$n - 1] + 

                              maxSumWO3Consec($n - 3));

}

  
// Код драйвера

$n = count($arr);

echo maxSumWO3Consec($n); 

  
// Этот код предоставлен mits
?>

Выход :

2101

Сложность времени: O (n)
Вспомогательное пространство: O (n)

Эта статья предоставлена Рошни Агарвал . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Максимальная сумма подпоследовательности, при которой три не являются последовательными

0.00 (0%) 0 votes