поиск максимального подмассива

[DenisVASI]

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

Код: (python) [Выделить]

__author__ = 'denis'
m = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]


def find_max_crossing_subarray(a, low, mid, high):
    left_sum = -1e308
    s = 0
    for i in range(mid, low, -1):
        s += a[i]
        if s > left_sum:
            left_sum = s
            max_left = i
    right_sum = -1e308
    s = 0
    for j in range(mid, high, 1):
        s += a[j]
        if s > right_sum:
            right_sum = s
            max_right = j
    return max_left, max_right, left_sum + right_sum


def find_max_subarray(a, low, high):
    if high == low:
        return low, high, a[low]
    else:
        mid = (low + high) / 2
        left_low, left_high, left_sum = find_max_subarray(a, low, mid)
        right_low, right_high, right_sum = find_max_subarray(a, mid, high)
        cross_low, cross_high, cross_sum = find_max_crossing_subarray(a, low, mid+1, high)
        if left_sum >= right_sum and left_sum >= cross_sum:
            return left_low, left_high, left_sum
        if right_sum >= left_sum and right_sum >= cross_sum:
            return right_low, right_high, right_sum
        else:
            return cross_low, cross_high, cross_sum

min, max, sum = find_max_subarray(m, 0, 15)

print(min, max, sum)
по ошибке я понял, что достигается предел глубины рекурсии, но сомневаюсь что нужно 1000 итераций для массива на 16 элементов
Пользователь решил продолжить мысль 30 Июля 2015, 16:26:00:добавление этого кода не помогло :

Код: (python) [Выделить]

import sys
sys.setrecursionlimit(100000)


[Azure]

Будет проще если Вы объясните условие задачи (что-то подобное я уже встречал и делалось оно на порядок проще)

[alsoijw]

DenisVASI, как это макс.подмассив?

[DenisVASI]

подмассив с максимальной суммой элементов, т.е a = [-1, 4, -3, 5, -1], максимальным будет 4, -3, 5
или другой пример использующий этот алгоритм http://habrahabr.ru/post/129576/ ,кстати эта программа тоже не работает
 
Пользователь решил продолжить мысль [time]30 Июль 2015, 20:41:30[/time]:Azure, вы правы можно проще, но есть я хочу знать рекурсивное решение,
к тому-же если я правильно понимаю этот алгоритм работает за время n lg n, а приведенные ниже варианты за n^2, хотя могу ошибаться, я ведь только учусь

Код: (python) [Выделить]

__author__ = 'denis'
a = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]

s = 0
ans = a[0]
ans_l = 0
ans_r = 0
min_sum = 0
min_pos = -1
[code = python]
for i in range(len(a)):
    s += a[i]
    cur = s - min_sum
    if cur > ans:
        ans = cur
        ans_l = min_pos + 1
        ans_r = i
    if s < min_sum:
        min_sum = s
        min_pos = i

print(ans, ans_l, ans_r)


Код: (python) [Выделить]

__author__ = 'denis'
a = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]

answer = 0
answer_l = 0
answer_r = 0
s = 0
minus_pos = -1

for i in range(len(a)):
    print(j)
    s += a[i]
    if s > answer:
        answer = s
        answer_l = minus_pos + 1
        answer_r = i
    if s < 0:
        s = 0
        minus_pos = i

print(answer, answer_l, answer_r)
Пользователь решил продолжить мысль [time]30 Июль 2015, 20:52:55[/time]:Вот оригинал текста задачи: http://rghost.ru/7vlNsqn6b#

[Azure]

Не увлекайтесь рекурсией, не здорово это:

Код: (python) [Выделить]

def max_sum_part(my_list):
    max_sum = 0
    list_length = len(my_list)
    r_border = list_length + 1
    for i in range(list_length):
        for j in range(i + 1, r_border):
            sum_part = sum(my_list[i:j]):
            if sum_part > max_sum:
                max_sum, left, right = sum_part, i, j - 1
    return (max_sum, left, right)Или можно сократить используя генераторы:

Код: (python) [Выделить]

def max_sum_part(my_list):
    return max((sum(a[i:j]),i,j - 1) for i in range(len(a)) for j in range(i + 1, len(a) + 1))

[DenisVASI]

Не увлекаюсь, но в книге целая глава этому посвящена, мне хочется знать как она работает.Тем более мой код не работает.Раз не работает, значит есть пробел в знаниях, вот и подскажите где он, пожалуйста)
Пользователь решил продолжить мысль 31 Июля 2015, 11:12:17:И ещё, а чем она(рекурсия) так плоха? Недавно общался с хаскелистом, так он говорит что у нее репутация как у goto в мире функциональных яп.

[SkinnyJack]

Не увлекаюсь, но в книге целая глава этому посвящена, мне хочется знать как она работает.Тем более мой код не работает.Раз не работает, значит есть пробел в знаниях, вот и подскажите где он, пожалуйста)
Пользователь решил продолжить мысль [time]31 Июль 2015, 12:12:17[/time]:И ещё, а чем она(рекурсия) так плоха? Недавно общался с хаскелистом, так он говорит что у нее репутация как у goto в мире функциональных яп.

Скорее всего проблема в условиях выхода из рекурсии. Прогоните по шагам.

Рекурсия, в принципе, не может быть плохой или хорошей. Это инструмент, как и goto. Другое дело, что можно переполнить стэк при большом уровне вложенности, к тому же, неуместное использование рекурсии, как и goto, приводит к излишней запутанности кода(это, наверное, и имел в виду ваш знакомый). Посмотрите на ту же реализацию алгоритма вычисления факториала, на quicksort, на алгоритмы обхода бинарных деревьев(которые сами по себе рекурсивны) - там рекурсия смотрится органично и не мешает восприятию. Уж не знаю  что у вас там за книжка, но настоятельно рекомендую "Алгоритмы + струкуры данных = программы" Никлауса Вирта.

[Sly_tom_cat]

Я вот не понял зачем в этой задаче рекурсия? 

Все три предложенных решения (после исправления незначительных ошибок) работают и дают одинаковый результат, причем однопроходный вариант - быстрее:

Код: [Выделить]

(43, 7, 10)

Execution time : 0.000191 s.

(43, 7, 10)

Execution time : 0.000179 s.

(43, 7, 10)

Execution time : 0.000023 s.


(Нажмите, чтобы показать/скрыть)

Код: (Python) [Выделить]

from time      import time

def max_sum_part(my_list):
    max_sum = 0
    list_length = len(my_list)
    r_border = list_length + 1
    for i in range(list_length):
        for j in range(i + 1, r_border):
            sum_part = sum(my_list[i:j])
            if sum_part > max_sum:
                max_sum, left, right = sum_part, i, j - 1
    return (max_sum, left, right)

def max_sum_part1(my_list):
    return max((sum(a[i:j]),i,j - 1) for i in range(len(a)) for j in range(i + 1, len(a) + 1))   

def max_sum_part2(a):
  answer = 0
  answer_l = 0
  answer_r = 0
  s = 0
  minus_pos = -1
 
  for i in range(len(a)):
    #print(i)
    s += a[i]
    if s > answer:
        answer = s
        answer_l = minus_pos + 1
        answer_r = i
    if s < 0:
        s = 0
        minus_pos = i
 
  return(answer, answer_l, answer_r)



if __name__ == '__main__':
  a = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
  startTime = time()
  print (max_sum_part(a))
  print('\nExecution time : %f s.\n'%(time() - startTime))
  startTime = time()
  print (max_sum_part1(a))
  print('\nExecution time : %f s.\n'%(time() - startTime))
  startTime = time()
  print (max_sum_part2(a))
  print('\nExecution time : %f s.\n'%(time() - startTime))


[Azure]

А еще проще не изобретать велосипед:

Код: (python) [Выделить]

def max_subarray(A):
    max_ending_here = max_so_far = A[0]
    for x in A[1:]:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

[Sly_tom_cat]

Azure, это решение дает только саму максимальную сумму. Как оттуда вытащить хоть один из индексов - я не понял. А без индексов поиск максимума дает только пол ответа.
У DenisVASI, решение тоже линейное время для решения требует, но дает полноценный ответ.

[Azure]

Как оттуда вытащить хоть один из индексов - я не понял. А без индексов поиск максимума дает только пол ответа.

Ну надо чуть доработать

Код: (python) [Выделить]

def max_subarray(A):
        max_ending_here = max_so_far = A[0]
        i=0
        for x in A[1:]:
                i+=1
                if max_ending_here < 0:
                        max_ending_here = x
                        start_here = i
                else:
                        max_ending_here += x
                if max_so_far < max_ending_here:
                        max_so_far, left, right = max_ending_here, start_here, i
        return max_so_far, left, right

[Sly_tom_cat]

Azure, ну по сути и получили решение как у DenisVASI.

[Azure]

Это не я, это Вики

Код: (python) [Выделить]

def max_subarray(A):
        max_ending_here = max_so_far = A[0]
        for x in enumerate(A[1:]):
                if max_ending_here < 0:
                        max_ending_here = x[1]
                        start = x[0]
                else:
                        max_ending_here += x[1]
                if max_so_far < max_ending_here:
                        max_so_far, left, right = max_ending_here, start, x[0]
        return max_so_far, left + 1, right + 1

[DenisVASI]

Книга: Алгоритмы - построение и Анализ, 3 издание, Томас Кормен.
Если кому не лень скачайте скан этой книги, и прочитайте стр.93-98. Там автор даёт пояснение почему его вариант как он считает лучше, я извиняюсь за излишнюю настойчивость, но на мой изначальный вопрос так ответа и не дали, где в моём коде ошибка? Найти иные решения я и сам сумел, проблема ведь именно в этой программе. Я не собираюсь пихать рекурсию везде, но я хочу сейчас понять как работает она в этой программе, я думал что понял, написал код, он не работает, опять же почему(код не работает)? А так всем спасибо, кто уделил внимание
Я понял что рекурсия тут может и не очень уместна, но раз этот код не работает, значит у меня есть пробел в знания, только даже ради этого стоит понять где там ошибка, тут ведь проблема где-то в записи кода, а не в моем понимании работы этого алгоритма, а значит и знания которые я тут получу будут распространяться на все мои будущие программы, так что помогите)

Пользователь решил продолжить мысль [time]31 Июль 2015, 21:34:50[/time]:http://scanlibs.com/algoritmyi-postroenie-i-analiz-3-e-izdanie/  - вот, можно тут взять

[Sly_tom_cat]

DenisVASI, я же поправил и запустил твой код. Правда в python3. Если у тебя не работает. То скопируй из моего сообщения и третьем питоне запусти - должно работаь.

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