| /trunk/languages/python/array-sum.py r13 | /trunk/languages/python/array-sum.py r14 | ||
| 1 | #!/usr/bin/python | 1 | #!/usr/bin/python |
|---|---|---|---|
| 2 | # -*- coding: utf-8 -*- | 2 | # -*- coding: utf-8 -*- |
| 3 | # | 3 | # |
| 4 | # Задача: в заданном массиве целых чисел найти отрезок с максимальной суммой. | 4 | # Задача: в заданном массиве целых чисел найти отрезок с максимальной суммой. |
| 5 | # Ссылка: http://www.cprogramming.com/challenges/array_sum.html | 5 | # Ссылка: http://www.cprogramming.com/challenges/array_sum.html |
| 6 | # Массив разрешается просматривать всего один раз. | 6 | # Массив разрешается просматривать всего один раз. |
| 7 | # Дополнительную память использовать нельзя. | 7 | # Дополнительную память использовать нельзя. |
| 8 | # | 8 | # |
| 9 | array = [3, -2, 1, 4, 5, 2, -7, 3] | 9 | array = [3, -2, 1, 4, 5, 2, -7, 3] |
| 10 | 10 | ||
| 11 | fsum = 0 | 11 | fsum = 0 |
| 12 | bsum = 0 | 12 | bsum = 0 |
| 13 | last = -1 | 13 | last = -1 |
| 14 | first = -1 | 14 | first = -1 |
| 15 | n = len (array) | 15 | n = len (array) |
| 16 | for i in range (0, n): | 16 | for i in range (0, n): |
| 17 | fsum += array[i] | 17 | fsum += array[i] |
| 18 | if array[i] > 0: | 18 | if array[i] > 0: |
| 19 | if last < 0 or fsum > fmax: | 19 | if last < 0 or fsum > fmax: |
| 20 | fmax = fsum | 20 | fmax = fsum |
| 21 | last = i | 21 | last = i |
| 22 | bsum += array[n-1-i] | 22 | bsum += array[n-1-i] |
| 23 | if array[n-1-i] > 0: | 23 | if array[n-1-i] > 0: |
| 24 | if first < 0 or bsum > bmax: | 24 | if first < 0 or bsum > bmax: |
| 25 | bmax = bsum | 25 | bmax = bsum |
| 26 | first = n-1-i | 26 | first = n-1-i |
| 27 | 27 | ||
| 28 | print "Array:", array | 28 | print "Array:", array |
| 29 | if first >= 0: | 29 | if first < 0: |
| 30 | print "Solution: empty subarray" | ||
| 31 | elif last >= first: | ||
| 30 | print "Solution:", array [first : last+1] | 32 | print "Solution:", array [first : last+1] |
| 33 | elif fmax >= bmax: | ||
| 34 | print "Solution:", array [ : last+1] | ||
| 31 | else: | 35 | else: |
| 32 | print "Solution: empty subarray" | 36 | print "Solution:", array [first : ] |
