Алгоритм Длинной Арифметической Прогрессии


Постановка Задачи: >

Дан отсортированный массив, найти длину самой длинной арифметической прогрессии в нем.

Примеры: числа = новый инт[]{1, 3, 4, 5, 7, 8, 9} Длина 5, и последовательность 1, 3, 5, 7, 9 с шагом 2 в каждой итерации.

Введение алгоритма

Алгоритм самой длинной арифметической прогрессии может быть решена с помощью метода динамического программирования. Я потратил несколько часов на изучение алгоритма. Я прочитал статью под названием "Найти длинные арифметические прогрессии", на основе авторской введение в бумаги, нижняя граница алгоритма o(nlogn) на основе алгебраической модели дерева принятия решений вычисления. Я постараюсь понять нижняя граница алгоритм позже, также Я люблю читать обзоры вопрос называется длинная равном расстоянии подпоследовательность на stackoverflow.com.

Динамическое программирование

Самой длинной арифметической прогрессии может быть найден в o(п.2) времени с помощью динамического программирования алгоритм аналогичен интересны следующие подзадачи , которые можно назвать средними.

Средняя подзадачи

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

Анализ теста

Мне нравится использовать матрицу 7 х 7 для определения таблицы подстановки на основе теста {1,3,4,5,7,8,9}.

Базовым вариантом является установка подстановки[я][н-1] = 2 для любого I от 0 до N - 1.

0 1 2 3 4 5 6
_________________________
0| 0 0 0 0 0 0 2
1| 0 0 0 0 0 0 2
2| 0 0 0 0 0 0 2
3| 0 0 0 0 0 0 2
4| 0 0 0 0 0 0 2
5| 0 0 0 0 0 0 2
6| 0 0 0 0 0 0 2

Проверить 8, в 7, 8, 9. У нас есть подстановок[4][5] = подстановок[5][6] + 1. Другими словами, 8 в среднем от 7 до 9, с 8 = (7 + 9)/ 2. Это тоже простой пример средняя подзадачи.

0 1 2 3 4 5 6
_________________________
0| 0 0 0 0 0 0 2
1| 0 0 0 0 0 0 2
2| 0 0 0 0 0 0 2
3| 0 0 0 0 0 0 2
4| 0 0 0 0 0 3 2
5| 0 0 0 0 0 0 2
6| 0 0 0 0 0 0 2

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

Практика пробных интервью

Мне сказали, на практике этот алгоритм, когда я практику пробных интервью 18 февраля, выходные 2018. Я написала решением C# на основе вышеуказанного теста. Алгоритм не слишком сложно, но это трудно для меня, чтобы выйти идея, чтобы определить подзадачи в среднем в первый раз.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TwoPointerTechniques
{
    class Program
    {
        /// <summary>
        /// Based on the code from the following blog:
        /// https://prismoskills.appspot.com/lessons/Dynamic_Programming/Chapter_22_-_Longest_arithmetic_progression.jsp
        /// </summary>
        /// <param name="args"></param>
        static void Main(string[] args)
        {
            var sortedArr = new int[] { 1, 3, 4, 5, 7, 8, 9 };
            var n = sortedArr.Length;
            var lookup = FindArithmeticProgressionLength3(sortedArr);

            Debug.Assert(lookup[0] == 5);
        }

        /// <summary>
        /// How to find if a sorted array contains an Arithmetic Progression (AP) of length 3?
        /// </summary>
        /// <param name="numbers"></param>
        /// <returns></returns>
        public static int[] FindArithmeticProgressionLength3(int[] numbers)
        {
            var n = numbers.Length;
            var lookup = new int[n][];

            for (int i = 0; i < n; i++)
            {
                lookup[i] = new int[n];
            }

            int maxAP = 2;

            int apTerm = 0;
            int apStart = 0;

            // Any 2-letter series is an AP
            // Here we initialize only for the last column of lookup because
            // all i and (n-1) pairs form an AP of size 2  
            for (int i = 0; i < n; i++)
            {
                lookup[i][n - 1] = 2;
            }

            // Loop over the array and find two elements 'left' and 'right' such that 
            // numbers[left] + numbers[right] = 2 * numbers[middle]
            for (int middle = n - 2; middle >= 1; middle--)
            {
                var left = middle - 1;
                var right = middle + 1;

                while (left >= 0 && right <= n - 1)
                {
                    int isAP = (numbers[left] + numbers[right]) - 2 * numbers[middle];

                    if (isAP < 0)
                    {
                        right++;
                    }
                    else if (isAP > 0)
                    {
                        left--;
                    }
                    else
                    {
                        lookup[left][middle] = lookup[middle][right] + 1;

                        maxAP = Math.Max(maxAP, lookup[left][middle]);

                        if (maxAP == lookup[left][middle])
                        {
                            // Store the Arithmetic Progression's term
                            // And the start point of the AP
                            apTerm = numbers[middle] - numbers[left];
                            apStart = left;
                        }

                        right++;
                        left--;
                    }
                }
            }

            return new int[] { maxAP, apStart, apTerm };
        }
    }
}


Комментарии
1 ответ

В FindArithmeticProgressionLength3 это всегда массив размерности n x n. Почему вы используете массивов массивов вместо

var lookup = new int[n, n];

// several lines skipped ...

for (var i = 0; i < n; i++)
{
lookup[i, n - 1] = 2;
}

Как 2-мерный массив только один объект по сравнению с N+1 объектов в многомерном массиве следует использовать, что. А также риск невозможности инициализировать массив (либо забыть один из lookup[n] для выделения или из-за памяти исключением) сводится к одной строке кода.

1
ответ дан 24 февраля 2018 в 10:02 Источник Поделиться