| /trunk/languages/python/array-sum.py r15 | /trunk/languages/python/array-sum.py r16 | ||
| 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 | #array = [3, -2, 1, 4, 5, 2, -7, 3, -100, 90] | 10 | #array = [3, -2, 1, 4, 5, 2, -7, 3, -100, 90] |
| 11 | #array = [1, -100, 2, -100, 1] | 11 | #array = [1, -100, 2, -100, 1] |
| 12 | #array = [-7, -2, -3] | 12 | #array = [-7, -2, -3] |
| 13 | 13 | ||
| 14 | sum = 0 | 14 | sum = 0 |
| 15 | bsum = 0 | 15 | bsum = 0 |
| 16 | maxsum = 0 | 16 | maxsum = 0 |
| 17 | last = -1 | 17 | last = -1 |
| 18 | first = 0 | 18 | first = 0 |
| 19 | bottom = 0 | 19 | bottom = 0 |
| 20 | maxneg = 0 | 20 | maxneg = 0 |
| 21 | for i in range (0, len (array)): | 21 | for i in range (0, len (array)): |
| 22 | sum += array[i] | 22 | sum += array[i] |
| 23 | if array[i] > 0: | 23 | if array[i] > 0: |
| 24 | if sum - bsum > maxsum: | 24 | if sum - bsum > maxsum: |
| 25 | first = bottom | 25 | first = bottom |
| 26 | last = i | 26 | last = i |
| 27 | maxsum = sum - bsum | 27 | maxsum = sum - bsum |
| 28 | # print "[%d]=%d: first=%d, last=%d" % (i, array[i], first, last) | ||
| 29 | else: | 28 | else: |
| 30 | if sum < bsum: | 29 | if sum < bsum: |
| 31 | bottom = i+1 | 30 | bottom = i+1 |
| 32 | bsum = sum | 31 | bsum = sum |
| 33 | # print "[%d]=%d: bottomt=%d" % (i, array[i], bottom) | ||
| 34 | if maxneg >= 0 or array[i] > maxneg: | 32 | if maxneg >= 0 or array[i] > maxneg: |
| 35 | maxneg = array[i] | 33 | maxneg = array[i] |
| 36 | 34 | ||
| 37 | print "Array:", array | 35 | print "Array:", array |
| 38 | #print "first =", first, "last =", last, "bottom =", bottom | ||
| 39 | if first <= last: | 36 | if first <= last: |
| 40 | print "Solution:", array [first : last+1] | 37 | print "Solution:", array [first : last+1] |
| 41 | else: | 38 | else: |
| 42 | print "Solution:", [maxneg] | 39 | print "Solution:", [maxneg] |
