Ответ 1

Вы можете сделать это в линейном (O (n)) времени:

def max_length(s, k):
    # These two mark the start and end of the subarray that `current` used to be.
    subarray_start = 0
    subarray_end = 0

    subarray_sum = 0
    max_len = -1 # returns -1 if there is no subsequence that adds up to k.
    for i in s:
        subarray_sum += i
        subarray_end += 1
        while subarray_sum > k: # Shrink the array from the left, until the sum is <= k.
            subarray_sum -= s[subarray_start]
            subarray_start += 1

        # After the previous while loop, subarray_sum is guaranteed to be 
        # smaller than or equal to k.
        max_len = max(max_len, subarray_end - subarray_start)

    return max_len

Была некоторая путаница с исходным вопросом, где я думал, что мы ищем подмассиву с суммой **, равной (но не менее) k *. Мой первоначальный ответ ниже. Там также содержится информация о линейности этого решения, поэтому читайте, если вам интересно.

Оригинальный ответ

Вот как бы я это сделал:

def max_length(s, k):
    current = []
    max_len = -1 # returns -1 if there is no subsequence that adds up to k.
    for i in s:
        current.append(i)
        while sum(current) > k: # Shrink the array from the left, until the sum is <= k.
           current = current[1:]
        if sum(current) == k:
            max_len = max(max_len, len(current))

    return max_len

Это использует тот факт, что мы ищем непрерывный подмассив для получения решения с линейной (O (n)) временной сложностью. current - наша текущая попытка создания подмассива, которая добавляет до k. Переходим через s и добавляем каждый элемент от s до current. Если общая сумма current становится слишком большой (больше, чем k), мы удаляем элементы слева от current, пока сумма не станет меньше или равна k. Если в любой точке сумма равна k, мы записываем длину.

Хорошо... Я солгал, и Франсиско Кузо поймал меня в комментариях. Код выше не является действительно O (n) Я вызываю len(current) и sum(current), которые принимают не более n шаги, заставляя алгоритм работать в квадратичном времени (O (n ^ 2)). Мы можем исправить это, следя за размером и суммой current самих себя.

Следующая версия приближает нас к O (n), но я заметил проблему при написании.

def max_length(s, k):
    current = []
    len_current = 0
    sum_current = 0
    max_len = -1 # returns -1 if there is no subsequence that adds up to k.
    for i in s:
        current.append(i)
        sum_current += i
        len_current += 1
        while sum_current > k: # Shrink the array from the left, until the sum is <= k.
            sum_current -= current[0]
            current = current[1:]
            len_current -= 1
        if sum_current == k:
            max_len = max(max_len, len_current)

    return max_len

Этот фрагмент кода может выглядеть так, как O (n), и если бы он был написан в Go, это было бы. Смотрите, что current = current[1:]? Согласно статье TimeComplexities в вики Python, взятие фрагмента из списка занимает O (n).

Я не смог найти операцию списка, которая удаляет элемент с самого начала, пока я не понял, что мне это не нужно. current всегда будет смежным подмассивом s, так почему бы просто не отметить его начало и конец?

Итак, мое окончательное решение:

def max_length(s, k):
    # These two mark the start and end of the subarray that `current` used to be.
    subarray_start = 0
    subarray_end = 0

    subarray_sum = 0
    max_len = -1 # returns -1 if there is no subsequence that adds up to k.
    for i in s:
        subarray_sum += i
        subarray_end += 1
        while subarray_sum > k: # Shrink the array from the left, until the sum is <= k.
            subarray_sum -= s[subarray_start]
            subarray_start += 1
        if subarray_sum == k:
            max_len = max(max_len, subarray_end - subarray_start)

    return max_len

Если вы считаете массив круглым, что, по-видимому, указывает первый пример в вопросе, вы можете пройти через массив дважды:

def max_length(s, k):
    s = s + s
    # These two mark the start and end of the subarray that `current` used to be.
    subarray_start = 0
    subarray_end = 0

    subarray_sum = 0
    max_len = -1 # returns -1 if there is no subsequence that adds up to k.
    for i in s:
        subarray_sum += i
        subarray_end += 1
        while subarray_sum > k: # Shrink the array from the left, until the sum is <= k.
            subarray_sum -= s[subarray_start]
            subarray_start += 1
        if subarray_sum == k:
            max_len = max(max_len, subarray_end - subarray_start)

    return max_len

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

Ответ 2

Оригинальный ответ

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

Вы можете запускать индексы списка, принимать каждый индекс в качестве начальной точки окна, по которому вы суммируете. Затем вы пробегаете индексы от начального индекса до конца, чтобы пометить конец окна. На каждом шаге вы берете сумму или, что еще лучше, добавляете ее к сумме. Если сумма превышает цель, вы выходите из внутреннего цикла, двигайтесь дальше.

Он будет выглядеть следующим образом:

def get_longes(a_list, k):
    longest = 0
    length = len(a_list)
    for i in xrange(length):
        s = 0
        for j in xrange(i,length):
            s+=a_list[j]
            if s < k:
                pass
            elif s==k:
                longest = j+1-i
            else:
                break
    return longest

Это может быть дополнительно ускорено, так как вам не нужно reset размер окна, когда вы перемещаете один шаг во внешнем цикле. На самом деле вам просто нужно отслеживать размер окна и уменьшать его на 1, если внешний контур перемещается. Таким образом, вы даже можете избавиться от внутреннего цикла и написать что-то в O (n):

def get_longest(a_list,k):
    length=len(a_list)
    l_length = 0
    longest = 0
    s = 0
    for i in xrange(length):
        while s<k:  # while the sum is smaller, we increase the window size
            if i+l_length==length: # this could also be handled with a try, except IndexError on the s+=a_list[... line
                return longest
            s+=a_list[i+l_length]
            l_length+=1
        if s == k:  # if the sum is right, keep its length if it is bigger than the last match.
            longest = max(l_length, longest)
        l_length-=1  # keep the window end at the same position (as we will move forward one step)
        s-=a_list[i]  # and subtract the element that will leave the window
    return longest

Ответ на обновленный вопрос

В обновленном вопросе задается самый длинный подмассив, для которого сумма равна или меньше k.

В этом вопросе основной подход тот же, и на самом деле решение становится еще проще, так как теперь у нас есть только два условия на сумму:

1) сумма меньше или равна k.

2) сумма больше k.

Решение выглядит так:

def get_longest_smaller_or_equal(a_list,k):
    length=len(a_list)
    l_length = 0
    longest = 0
    s = 0
    for i in xrange(length):
        while s<=k:  # while the sum is smaller, we increase the window size
            longest = max(l_length, longest)
            if i+l_length==length: # this could also be handled with a try, except IndexError on the s+=a_list[... line
                return longest
            s+=a_list[i+l_length]
            l_length+=1
        l_length-=1  # keep the window end at the same position (as we will move forward one step)
        s-=a_list[i]  # and subtract the element that will leave the window
    return longest

Ответ 3

Я думаю, что это работает... (рекурсивно и вынимая смежное требование из вопроса, поскольку это, похоже, не соответствует выборочным выводам, предоставленным в вопросе), и OP упоминает, что вопрос был:

задан некоторый массив положительных целых чисел s, найдите длину самого длинного подмассива, так что сумма всех значений равна некоторому положительному числу k.

def longest_sum(input_list, index, num_used, target_number):
    if target_number == 0:
        return num_used
    if index >= len(input_list):
        return 0

    # Taken
    used_1 = longest_sum(input_list, index + 1, num_used + 1, target_number - input_list[index])
    # Not taken
    used_2 = longest_sum(input_list, index + 1, num_used, target_number)
    return max(used_1, used_2)


if __name__ == "__main__":
    print(longest_sum([2, 1, 8, 3, 4], 0, 0, 6))
    print(longest_sum([1, 2, 3], 0, 0, 4))
    print(longest_sum([3, 1, 2, 1], 0, 0, 4))
    print(longest_sum([1, 2, 7, 8, 11, 12, 14, 15], 0, 0, 10))
    print(longest_sum([1, 2, 3], 0, 0, 999))
    print(longest_sum([1, 1, 1, 1, 1, 1, 4], 0, 0, 6))

Выходы:

3
# BorrajaX note: 2 + 1 + 3
2
# BorrajaX note: 3 + 1
3
# BorrajaX note: 1 + 2 + 1
3
# BorrajaX note: 1 + 2 + 7
0
# BorrajaX note: No possible sum
6
# BorrajaX note: 1 + 1 + 1 + 1 + 1 + 1

РЕДАКТИРОВАТЬ 01:

Если вы хотите получить список, который дает вам самую длинную сумму, вы всегда можете сделать это следующим образом:

import copy


def longest_sum(input_list, used_list, target_number):
    if target_number == 0:
        return used_list

    if not input_list:
        return []

    # Taken
    used_list_taken = copy.copy(used_list)
    used_list_taken.append(input_list[0])
    used_1 = longest_sum(input_list[1:], used_list_taken, target_number - input_list[0])

    # Not taken
    used_list_not_taken = copy.copy(used_list)
    used_2 = longest_sum(input_list[1:], used_list_not_taken, target_number)
    if len(used_1) > len(used_2):
        return used_1
    else:
        return used_2


if __name__ == "__main__":
    print(longest_sum([2, 1, 8, 3, 4], [], 6))
    print(longest_sum([1, 2, 3], [], 4))
    print(longest_sum([3, 1, 2, 1], [], 4))
    print(longest_sum([1, 2, 7, 8, 11, 12, 14, 15], [], 10))
    print(longest_sum([1, 2, 3], [], 999))
    print(longest_sum([1, 1, 1, 1, 1, 1, 4], [], 6))

Вы увидите:

[2, 1, 3]
[1, 3]
[1, 2, 1]
[1, 2, 7]
[]
[1, 1, 1, 1, 1, 1]

PS 1: Я действительно не знаю, как это сделать без возможностей быстрого возврата, которые рекурсия предоставляет... Извините : - (

PS 2: Если это не то, что вы хотели (я упомянул, что я взял неотъемлемое требование из требований), дайте мне знать, и я удалю этот ответ.

Ответ 4

Вот решение, которое работает для любого итеративного s (даже итератора). Это по сути тот же алгоритм, что и ответ со стороны большого блайнда, но будет более эффективным, если k велико по отношению к значениям в s (так что длины соответствующих подпоследовательности длинны):

import itertools

def max_length(s, k):
    head, tail = itertools.tee(s)
    current_length = current_sum = 0
    max_len = -1 # returns -1 if there is no subsequence that adds up to k.

    for i in head:
        current_length += 1
        current_sum += i

        while current_sum > k:
           current_length -= 1
           current_sum -= next(tail)

        if current_sum == k:
            max_len = max(max_len, current_sum)

    return max_len

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

Если вы хотите получить копию самой длинной подпоследовательности, вы можете использовать другую вариацию для ответа на большой ответ, используя collections.dequeue вместо списка (так, чтобы поскользнуться слева быстро) и отслеживание работы как мой код (так что вам не нужно снова и снова звонить sum):

import collections

def max_subsequence(s, k):
    current = collections.dequeue()
    current_sum = 0
    max_len = -1
    max_seq = None # returns None if there is no valid subsequence.

    for i in s:
        current.append(i)
        current_sum += i

        while current_sum > k: # Shrink from the left efficiently!
           current_sum -= current.popleft()

        if current_sum == k:
            if len(current) > max_len:
                max_len = len_current
                max_seq = list(current) # save a copy of the subsequence

    return max_seq

Если ваш заголовок вопроса вводит в заблуждение, и вы действительно не заботитесь о непрерывности подпоследовательности, я думаю, что ваш текущий подход к динамическому программированию может делать то, что вы хотите. Я просто не совсем уверен, что понимаю, как ваши петли должны были работать. Я думаю, что это наиболее естественно с внешним циклом над входными элементами и вторым циклом над потенциальными суммами, которые включают это значение (которые являются индексами в список lengths). Я также предложил бы использовать None в качестве начального значения для всех длин, отличных от 0, так как в противном случае его трудно сделать условия корректными без особых случаев.

def max_length(s, k):
    lengths = [None for _ in range(k+1)]
    lengths[0] = 0

    for x in s:
        for i in range(k, x-1, -1): # count down to avoid duplication
            if lengths[i-x] is not None and (lengths[i] is None or
                                             lengths[i-x] >= lengths[i]):
                lengths[i] = lengths[i-x] + 1

    return lengths[k]

Ответ 5

Бит короче и предполагает некруглые s: слайд-окна с уменьшением размера по s.

def maxlen(s, k):
    for win in range(k, 0, -1):
        for i in range(0, len(s) - win):
            if sum(s[i:i+win]) == k:
                return win
    return None

s = [3,1,2,3]
k = 4
print(maxlen(s, k))

Ответ 6

Подходы к этой проблеме

O (n) - подход с двумя указателями

Инициализировать первый элемент для s и e и subArray_sum = arr [0]

Теперь, если subArray_sum < k increment e while subArray_sum <= k

Как только subArray_sum станет >= k increment s, пока он не станет <= k

O (nlog n) - Двоичный поиск

Рассмотрим все возможные длины подмассивов i. (1 <= я <= n). По всем подматрицам длины я найдите ту, у которой минимальная сумма. Для заданного значения я это можно сделать в O (n). Теперь для любого подматрицы длины i, если подмассив длины i, но с минимальной суммой, имеет сумму <= k, мы можем найти я массивы длины с суммой <= k. Теперь найти самый длинный я такой, что существует Subarray этой длины с суммой sub array <= k. Делайте бинарный поиск по диапазону я с началом = 1 и end = n;

O (n * n) - грубая сила

Рассмотрим все возможные подмассивы (n * n в числе) и найдем наиболее длинными с суммой <= k

Вариант проблемы выше

Длина самого длинного подмассива со средним значением, меньшим или равным k

Все вышеприведенные подходы, применимые здесь, также

Ответ 7

Эта статья может вам очень помочь.

https://e2718281828459045.wordpress.com/2013/08/19/longest-subarray-whose-sum-k/

Его можно решить, используя
Sum Array + Binary Search.

Первое наблюдение, которое вы получаете, состоит в том, что если мы рассмотрим элемент я ^th то мы должны продолжить (i + 1) ^th и так далее. То есть нам нужно добавить все элементы в порядке до последнего элемента или мы достигнем суммы. Поэтому порядок важен.

Как мы можем добавить числа. Существует n способов. Первый способ состоит в том, что мы можем начинать с первого элемента и добавлять до достижения k или доходить до последнего элемента. Второй способ состоит в том, что мы можем начинать со второго элемента и читать, пока не достигнем k или не достигнем последнего элемента.

Итак, алгоритм грубой силы даст вам O (n ²) решение. Как мы можем улучшить это? Очевидно, что это не ожидаемое решение. Для каждого i

мы вычисляем сумму элемента и проверяем, что сумма превышает заданное значение "k" или нет. Чтобы этого избежать, мы можем создать массив сумм.

Помните, что всякий раз, когда вы сталкиваетесь с проблемой с суммой последовательности (или суммой непрерывных элементов в заданном массиве), скорее всего, она может решить с использованием метода суммарного массива. Массив Sum - это новый массив, использующий данный массив. Он может быть сгенерирован по следующей формуле:

sum[i] = sum[i−1] + array[i]

для всех i > 0. и

sum[i]=array[i]

для я = 0.

Массив Sum может быть создан в O (n) времени. Найти сумму между я ^th и j ^th становится легко. Это разница,

sum[j]−sum[i], j>i

даст вам ответ. Но все же это решение O (n ²).
Проблема в том, что для каждого значения i мы берем O (n) время, чтобы найти j.
Итак, как мы можем уменьшить это?
Бинго! Здесь идет двоичный поиск. Используя измененный бинарный поиск на интервале i и n для каждого i, мы можем найти время j в O (logn). Поэтому требуется только время O (nlogn). Нам нужна дополнительная переменная и условие для хранения длины подмассива, то есть j−i.

Надеюсь, что это поможет.