Рубрики

Длинная арифметическая прогрессия | DP-35

Учитывая набор чисел, найти L ength из L ongest A rithmetic P rogression (LLAP) в нем.

Примеры:

set[] = {1, 7, 10, 15, 27, 29}
output = 3
The longest arithmetic progression is {1, 15, 29}

set[] = {5, 10, 15, 20, 25, 30}
output = 6
The whole set is in AP

Для простоты мы предположили, что данное множество отсортировано. Мы всегда можем добавить шаг предварительной обработки, чтобы сначала отсортировать набор, а затем применить приведенные ниже алгоритмы.

Простое решение состоит в том, чтобы один за другим рассматривать каждую пару как первые два элемента AP и проверять оставшиеся элементы в отсортированном множестве. Чтобы рассматривать все пары как первые два элемента, нам нужно запустить вложенный цикл O (n ^ 2). Внутри вложенных циклов нам нужен третий цикл, который линейно ищет больше элементов в A Rithmetic P rogression ( AP ). Этот процесс занимает O (n 3 ) времени.

Мы можем решить эту проблему за время O (n 2 ), используя динамическое программирование . Чтобы получить представление о решении DP, давайте сначала обсудим решение следующей более простой задачи.

Учитывая отсортированный набор, найдите, существуют ли три элемента в Арифметической прогрессии или нет
Обратите внимание, что ответ верен, если в AP есть 3 или более элементов, в противном случае — ложь.
Чтобы найти три элемента, мы сначала фиксируем элемент как средний элемент и ищем другие два (один меньший и один больший). Мы начинаем со второго элемента и фиксируем каждый элемент как средний элемент. Чтобы набор элементов [j] находился посередине AP, должны существовать элементы 'set [i]' и 'set [k]', чтобы set [i] + set [k] = 2 * set [j], где 0 <= i <j и j <k <= n-1.
Как эффективно найти I и K для данного J? Мы можем найти i и k за линейное время, используя следующий простой алгоритм.

  1. Инициализируйте i как j-1 и k как j + 1
    • Делайте следующее, пока i> = 0 и j <= n-1

    • Если set [i] + set [k] равно 2 * set [j], то все готово.
    • Если set [i] + set [k]> 2 * set [j], то уменьшить i (сделать i–).
    • Иначе, если set [i] + set [k] <2 * set [j], тогда увеличить k (сделать k ++).

Ниже приведена реализация C ++ вышеупомянутого алгоритма для более простой задачи.

// Функция возвращает true, если в AP есть три элемента
// Предположение: set [0..n-1] отсортировано.
// Код строго реализует алгоритм, представленный в ссылке.

bool arithmeticThree(int set[], int n)

{

    // Один за другим фиксируем каждый элемент как средний

    for (int j=1; j<n-1; j++)

    {

        // Инициализируем i и k для текущего j

        int i = j-1, k = j+1;

  

        // Найти, существуют ли i и k, которые образуют AP

        // с j в качестве среднего элемента

        while (i >= 0 && k <= n-1)

        {

            if (set[i] + set[k] == 2*set[j])

                return true;

            (set[i] + set[k] < 2*set[j])? k++ : i--;

        }

    }

  

    return false;

}

Смотрите это для полной работающей программы.

Как расширить вышеприведенное решение для исходной задачи?
Вышеуказанная функция возвращает логическое значение. Требуется выход исходной задачи L ength из L ongest rithmetic Р rogression (LLAP) , который представляет собой целое число значений. Если в данном наборе есть два или более элементов, то значение LLAP составляет не менее 2 (почему?).
Идея состоит в том, чтобы создать 2D-таблицу L [n] [n]. Запись L [i] [j] в этой таблице хранит LLAP с set [i] и набором [j] в качестве первых двух элементов AP и j> i. Последний столбец таблицы всегда равен 2 (Почему — см. Значение L [i] [j]). Остальная часть таблицы заполняется снизу справа вверху слева. Чтобы заполнить остальную часть таблицы, j (второй элемент в AP) сначала фиксируется. i и k ищутся с фиксированным j. Если i и k найдены такими, что i, j, k образуют AP, то значение L [i] [j] устанавливается как L [j] [k] + 1. Обратите внимание, что значение L [j] [k] должно быть заполнено до того, как цикл пересекает столбцы справа налево.

Ниже приведена реализация алгоритма динамического программирования.

C ++

// C ++ программа для поиска длины самого длинного AP (llap) в заданном отсортированном наборе.
// Код строго реализует алгоритм, представленный в ссылке.
#include <iostream>

using namespace std;

  
// Возвращает длину самого длинного подмножества AP в данном наборе

int lenghtOfLongestAP(int set[], int n)

{

    if (n <= 2)  return n;

  

    // Создать таблицу и инициализировать все значения как 2. Значение

    // L [i] [j] сохраняет LLAP с set [i] и set [j] как первые два

    // элементы AP. Только действительные записи - это записи, где j> i

    int L[n][n];

    int llap = 2;  // Инициализируем результат

  

    // Заполняем записи в последнем столбце как 2. Всегда будет

    // два элемента в AP с последним номером, установленным в качестве второго

    // элемент в AP

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

        L[i][n-1] = 2;

  

    // Рассмотрим каждый элемент как второй элемент AP

    for (int j=n-2; j>=1; j--)

    {

        // Поиск i и k для j

        int i = j-1, k = j+1;

        while (i >= 0 && k <= n-1)

        {

           if (set[i] + set[k] < 2*set[j])

               k++;

  

           // Перед изменением i устанавливаем L [i] [j] как 2

           else if (set[i] + set[k] > 2*set[j])

           {   L[i][j] = 2, i--;   }

  

           else

           {

               // Найдены i и k для j, LLAP с i и j в качестве первых двух

               // элементы равны LLAP с j и k как первые два

               // элементы плюс 1. L [j] [k] должно быть заполнено

               // до того как мы запустим цикл с правой стороны

               L[i][j] = L[j][k] + 1;

  

               // Обновить общий LLAP, если необходимо

               llap = max(llap, L[i][j]);

  

               // Изменим i и k, чтобы заполнить больше значений L [i] [j] для

               // текущий j

               i--; k++;

           }

        }

  

        // Если цикл был остановлен из-за того, что k становится больше

        // n-1, устанавливаем оставшиеся записи в столбце j как 2

        while (i >= 0)

        {

            L[i][j] = 2;

            i--;

        }

    }

    return llap;

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

    int set1[] = {1, 7, 10, 13, 14, 19};

    int n1 = sizeof(set1)/sizeof(set1[0]);

    cout <<   lenghtOfLongestAP(set1, n1) << endl;

  

    int set2[] = {1, 7, 10, 15, 27, 29};

    int n2 = sizeof(set2)/sizeof(set2[0]);

    cout <<   lenghtOfLongestAP(set2, n2) << endl;

  

    int set3[] = {2, 4, 6, 8, 10};

    int n3 = sizeof(set3)/sizeof(set3[0]);

    cout <<   lenghtOfLongestAP(set3, n3) << endl;

  

    return 0;

}

Джава

// Java программа для поиска длины
// Самый длинный AP (llap) в данном отсортированном наборе.
// Код строго реализует
// алгоритм предоставлен в ссылке.

import java.io.*;

  

class GFG 

{

    // Возвращает длину самого длинного

    // Подмножество AP в данном наборе

    static int lenghtOfLongestAP(int set[], int n)

    {

        if (n <= 2) return n;

      

        // Создать таблицу и инициализировать все

        // значения как 2. Значение L [i] [j] сохраняет

        // LLAP с set [i] и set [j] в качестве первых двух

        // элементы AP. Только действительные записи

        // записи, где j> i

        int L[][] = new int[n][n];

          

         // Инициализируем результат

        int llap = 2;

      

        // Заполняем записи в последнем столбце как 2.

        // всегда будет два элемента в

        // AP с последним номером, установленным в качестве второго

        // элемент в AP

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

            L[i][n - 1] = 2;

      

        // Рассмотрим каждый элемент как второй элемент AP

        for (int j = n - 2; j >= 1; j--)

        {

            // Поиск i и k для j

            int i = j -1 , k = j + 1;

            while (i >= 0 && k <= n - 1)

            {

            if (set[i] + set[k] < 2 * set[j])

                k++;

      

            // Перед изменением i устанавливаем L [i] [j] как 2

            else if (set[i] + set[k] > 2 * set[j])

            

                L[i][j] = 2; i--; 

                  

            }

      

            else

            {

                // Найдены i и k для j, LLAP с i и j в качестве первых двух

                // элементы равны LLAP с j и k как первые два

                // элементы плюс 1. L [j] [k] должно быть заполнено

                // до того как мы запустим цикл с правой стороны

                L[i][j] = L[j][k] + 1;

      

                // Обновить общий LLAP, если необходимо

                llap = Math.max(llap, L[i][j]);

      

                // Изменить i и k для заполнения

                // больше значений L [i] [j] для текущего j

                i--; k++;

            }

            }

      

            // Если цикл был остановлен из-за

            // к становится больше чем

            // n-1, установить оставшиеся

            // записи в столбце j как 2

            while (i >= 0)

            {

                L[i][j] = 2;

                i--;

            }

        }

        return llap;

    }

      

    // Драйвер программы

    public static void main (String[] args) 

    {

        int set1[] = {1, 7, 10, 13, 14, 19};

        int n1 = set1.length;

        System.out.println ( lenghtOfLongestAP(set1, n1));

      

        int set2[] = {1, 7, 10, 15, 27, 29};

        int n2 = set2.length;

        System.out.println(lenghtOfLongestAP(set2, n2));

      

        int set3[] = {2, 4, 6, 8, 10};

        int n3 = set3.length;

        System.out.println(lenghtOfLongestAP(set3, n3)) ;

      

      

    }

}

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

Python 3

# Python 3 программа для поиска длины
# Самый длинный AP (ляп) в данном отсортированном наборе.
# Код строго реализует алгоритм
# предоставлено в ссылке

  
# Возвращает длину самого длинного AP
# подмножество в данном наборе

def lenghtOfLongestAP(set, n):

  

    if (n <= 2):

        return n

  

    # Создать таблицу и инициализировать все

    # значения как 2. Значение L [i] [j]

    # сохраняет LLAP с помощью set [i] и set [j]

    # как первые два элемента AP. Только

    # допустимые записи - это записи, где j> i

    L = [[0 for x in range(n)]

            for y in range(n)]

    llap = 2 # Инициализировать результат

  

    # Заполните записи в последнем столбце как 2.

    # Всегда будет два элемента

    # в AP с последним номером, установленным как

    # второй элемент в AP

    for i in range(n):

        L[i][n - 1] = 2

  

    # Рассматривать каждый элемент как второй

    # элемент AP

    for j in range(n - 2, 0, -1):

  

        # Поиск i и k для j

        i = j - 1

        k = j + 1

        while(i >= 0 and k <= n - 1):

  

            if (set[i] + set[k] < 2 * set[j]):

                k += 1

  

            # Перед изменением i установите L [i] [j] как 2

            elif (set[i] + set[k] > 2 * set[j]):

                L[i][j] = 2

                i -= 1

  

            else:

  

                # Найдены i и k для j, LLAP с i и j

                # так как первые два элемента равны LLAP

                # с j и k в качестве первых двух элементов плюс 1.

                # L [j] [k] должно быть заполнено до того как

                # запускаем цикл с правой стороны

                L[i][j] = L[j][k] + 1

  

                # Обновите общий LLAP, если необходимо

                llap = max(llap, L[i][j])

  

                # Измените i и k, чтобы заполнить больше L [i] [j]

                # значения для текущего j

                i -= 1

                k += 1

  

                # Если цикл был остановлен из-за k

                # становясь больше чем n-1, установите

                # оставшиеся записи в столбце j как 2

                while (i >= 0):

                    L[i][j] = 2

                    i -= 1

    return llap

  
Код водителя

if __name__ == "__main__":

      

    set1 = [1, 7, 10, 13, 14, 19]

    n1 = len(set1)

    print(lenghtOfLongestAP(set1, n1))

  

    set2 = [1, 7, 10, 15, 27, 29]

    n2 = len(set2)

    print(lenghtOfLongestAP(set2, n2))

  

    set3 = [2, 4, 6, 8, 10]

    n3 = len(set3)

    print(lenghtOfLongestAP(set3, n3))

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

C #

// C # программа для поиска длины
// Самый длинный AP (llap) в данном отсортированном наборе.
// Код строго реализует
// алгоритм предоставлен в ссылке.

using System;

  

class GFG

{
// Возвращает длину самого длинного
// Подмножество AP в данном наборе

static int lenghtOfLongestAP(int []set

                             int n) 

    if (n <= 2) return n; 

  

    // Создать таблицу и инициализировать

    // все значения как 2. Значение

    // L [i] [j] сохраняет LLAP с set [i]

    // и устанавливаем [j] в качестве первых двух элементов

    // из AP. Только действительные записи

    // записи, где j> i

    int [,]L = new int[n, n]; 

      

    // Инициализируем результат

    int llap = 2; 

  

    // Заполняем записи в последнем столбце как 2.

    // всегда будет два элемента

    // в точке доступа с последним номером, установленным как

    // второй элемент в AP

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

        L[i, n - 1] = 2; 

  

    // Рассмотрим каждый элемент как

    // второй элемент AP

    for (int j = n - 2; j >= 1; j--) 

    

        // Поиск i и k для j

        int i = j - 1 , k = j + 1; 

        while (i >= 0 && k <= n - 1) 

        

        if (set[i] + set[k] < 2 * set[j]) 

            k++; 

  

        // Перед изменением i устанавливаем L [i] [j] как 2

        else if (set[i] + set[k] > 2 * set[j]) 

        

            L[i, j] = 2; i--; 

              

        

  

        else

        

            // Найдены i и k для j, LLAP с

            // я и j как первые два элемента

            // равно LLAP с j и k

            // как первые два элемента плюс 1.

            // L [j] [k] должно быть заполнено

            // до того как мы запустим цикл из

            // правая сторона

            L[i, j] = L[j, k] + 1; 

  

            // Обновить общий LLAP, если необходимо

            llap = Math.Max(llap, L[i, j]); 

  

            // Изменить i и k для заполнения

            // больше значений L [i] [j] для текущего j

            i--; k++; 

        

        

  

        // Если цикл был остановлен из-за

        // к становится больше чем

        // n-1, установить оставшиеся

        // записи в столбце j как 2

        while (i >= 0) 

        

            L[i, j] = 2; 

            i--; 

        

    

    return llap; 

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

static public void Main ()

{

    int []set1 = {1, 7, 10, 13, 14, 19}; 

    int n1 = set1.Length; 

    Console.WriteLine(lenghtOfLongestAP(set1, n1)); 

  

    int []set2 = {1, 7, 10, 15, 27, 29}; 

    int n2 = set2.Length; 

    Console.WriteLine(lenghtOfLongestAP(set2, n2)); 

  

    int []set3 = {2, 4, 6, 8, 10}; 

    int n3 = set3.Length; 

    Console.WriteLine(lenghtOfLongestAP(set3, n3)) ;

}
}

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

PHP

<?php
// PHP программа для поиска длины
// Самый длинный AP (llap) в данном отсортированном наборе.

  
// Код строго реализует
// алгоритм предоставлен в ссылке.

  
// Возвращает длину самого длинного AP
// подмножество в данном наборе

function lenghtOfLongestAP($set, $n

    if ($n <= 2) 

        return $n

  

    // Создать таблицу и инициализировать все

    // значения как 2. Значение L [i] [j]

    // сохраняет LLAP с помощью set [i] и set [j]

    // как первые два элемента AP. Только

    // допустимые записи - это записи, где j> i

    $L[$n][$n] = array(array()); 

    $llap = 2; // Инициализируем результат

  

    // Заполняем записи в последнем столбце как 2.

    // всегда будет два элемента

    // в точке доступа с последним номером, установленным как

    // второй элемент в AP

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

        $L[$i][$n - 1] = 2; 

  

    // Рассмотрим каждый элемент как

    // второй элемент AP

    for ($j = $n - 2; $j >= 1; $j--) 

    

        // Поиск i и k для j

        $i = $j - 1;

        $k = $j + 1; 

        while ($i >= 0 && $k <= $n - 1) 

        

        if ($set[$i] + $set[$k] < 2 * $set[$j]) 

            $k++; 

  

        // Перед изменением i устанавливаем L [i] [j] как 2

        else if ($set[$i] + $set[$k] > 2 * $set[$j]) 

        

            $L[$i][$j] = 2;

            $i--; } 

  

        else

        

            // Найдены i и k для j, LLAP с

            // я и j как первые два элемента

            // равно LLAP с j и k

            // как первые два элемента плюс 1.

            // L [j] [k] должно быть заполнено

            // до того как мы запустим цикл из

            // правая сторона

            $L[$i][$j] = $L[$j][$k] + 1; 

  

            // Обновить общий LLAP, если необходимо

            $llap = max($llap, $L[$i][$j]); 

  

            // Изменить i и k, чтобы заполнить больше

            // L [i] [j] значения для текущего j

            $i--; 

            $k++; 

        

        

  

        // Если цикл был остановлен из-за k

        // становясь больше чем n-1, устанавливаем

        // оставшиеся записи в столбце j как 2

        while ($i >= 0) 

        

            $L[$i][$j] = 2; 

            $i--; 

        

    

    return $llap

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

$set1 = array(1, 7, 10, 13, 14, 19); 

$n1 = sizeof($set1); 

echo lenghtOfLongestAP($set1, $n1),"\n"

  

$set2 = array(1, 7, 10, 15, 27, 29); 

$n2 = sizeof($set2); 

echo lenghtOfLongestAP($set2, $n2),"\n"

  

$set3 = array(2, 4, 6, 8, 10); 

$n3 = sizeof($set3); 

echo lenghtOfLongestAP($set3, $n3),"\n"

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


Выход:

4
3
5

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

Как уменьшить сложность пространства для вышеуказанного решения?

Мы также можем уменьшить сложность пространства до O (n) .

Ниже приведена реализация алгоритма динамического программирования с пространственной сложностью O (n) .

C ++

// C ++ программа для поиска длины
// Самый длинный AP (llap) в данном отсортированном наборе.
#include <bits/stdc++.h>

  

using namespace std;

  
// Возвращает длину самого длинного
// Подмножество AP в данном наборе

int Solution(vector<int> A)

{

    int ans = 2;

    int n = A.size();

    if (n <= 2)

        return n;

  

    vector<int> llap(n, 2);

  

    sort(A.begin(), A.end());

  

    for (int j = n - 2; j >= 0; j--)

    {

        int i = j - 1;

        int k = j + 1;

        while (i >= 0 && k < n)

        {

            if (A[i] + A[k] == 2 * A[j])

            {

                llap[j] = max(llap[k] + 1, llap[j]);

                ans = max(ans, llap[j]);

                i -= 1;

                k += 1;

            }

            else if (A[i] + A[k] < 2 * A[j])

                k += 1;

            else

                i -= 1;

        }

    }

    return ans;

}

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

int main()

{

    vector<int> a({ 9, 4, 7, 2, 10 });

    cout << Solution(a) << endl;

    return 0;

}

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

Джава

// Java программа для поиска длины
// Самый длинный AP (llap) в данном отсортированном наборе.

import java.util.*;

  

class GFG

{

  
// Возвращает длину самого длинного
// Подмножество AP в данном наборе

static int Solution(int []A)

{

    int ans = 2;

    int n = A.length;

    if (n <= 2)

        return n;

  

    int []llap = new int[n];

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

        llap[i] = 2;

  

    Arrays.sort(A);

  

    for (int j = n - 2; j >= 0; j--)

    {

        int i = j - 1;

        int k = j + 1;

        while (i >= 0 && k < n)

        {

            if (A[i] + A[k] == 2 * A[j])

            {

                llap[j] = Math.max(llap[k] + 1, llap[j]);

                ans = Math.max(ans, llap[j]);

                i -= 1;

                k += 1;

            }

            else if (A[i] + A[k] < 2 * A[j])

                k += 1;

            else

                i -= 1;

        }

    }

    return ans;

}

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

public static void main(String[] args)

{

    int []a = { 9, 4, 7, 2, 10 };

    System.out.print(Solution(a) +"\n");

}
}

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

питон

# Python программа для поиска длины
# самого длинного AP (ляп) в данном отсортированном наборе.

    

 # Возвращает длину самого длинного подмножества AP в данном наборе

    

class Solution: 

    def Solve(self, A): 

        ans = 2        

        n= len(A) 

        if n<=2

            return

        llap = [2]*

        A.sort() 

    

        for j in range(n-2, -1, -1): 

            i= j-1

            k= j+1

            while(i>=0 and k<n): 

                if A[i]+A[k] == 2*A[j]: 

                    llap[j] = max(llap[k]+1,llap[j]) 

                    ans = max(ans, llap[j]) 

                    i-=1

                    k+=1

                elif A[i]+A[k] < 2*A[j]: 

                    k += 1

                else

                    i -= 1

    

        return ans  

    
# Программа драйвера для проверки вышеуказанной функции

obj = Solution() 

a= [9, 4, 7, 2, 10

print(obj.Solve(a)) 

C #

// C # программа для поиска длины
// самое длинное AP (llap) в данном отсортированном наборе.

using System;

  

class GFG

{

  
// Возвращает длину самого длинного
// Подмножество AP в данном наборе

static int Solution(int []A)

{

    int ans = 2;

    int n = A.Length;

    if (n <= 2)

        return n;

  

    int []llap = new int[n];

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

        llap[i] = 2;

  

    Array.Sort(A);

  

    for (int j = n - 2; j >= 0; j--)

    {

        int i = j - 1;

        int k = j + 1;

        while (i >= 0 && k < n)

        {

            if (A[i] + A[k] == 2 * A[j])

            {

                llap[j] = Math.Max(llap[k] + 1, llap[j]);

                ans = Math.Max(ans, llap[j]);

                i -= 1;

                k += 1;

            }

            else if (A[i] + A[k] < 2 * A[j])

                k += 1;

            else

                i -= 1;

        }

    }

    return ans;

}

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

public static void Main(String[] args)

{

    int []a = { 9, 4, 7, 2, 10 };

    Console.Write(Solution(a) +"\n");

}
}

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


Выход:

3

Сложность времени: O (n 2 )
Вспомогательное пространство: O (n)
Вышеупомянутое решение представлено Умангом Гуптой

Ссылки:
http://www.cs.uiuc.edu/~jeffe/pubs/pdf/arith.pdf

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

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

Длинная арифметическая прогрессия | DP-35

0.00 (0%) 0 votes