[アルゴリズム]リング配列の中和値の最大サブセグメントを求める

非環状配列について、和値の最大サブセグメントを解く方法は前の文章を参照する.
リング配列の場合、最大和値サブセグメントが先頭境界を越える場合を考慮する必要があり、解決方法は比較的簡単で、配列を2回処理する.サブセグメントの長さは配列全体の長さを超えてはならないことに注意してください.
 

 1 #! -*- coding: utf-8 -*-
 2 
 3 loop = (4, -3, 2, -4, 1, 5, -3, -4, 3)
 4 #loop = (4, 3, 2, 4, 1, 5, 3, 4, 3)
 5 #loop = (-4, -3, -2, -4, -1, -5, -3, -4, -3)
 6 
 7 #         
 8 #                    ，     
 9 #    O(n)
10 #        ，      ，               
11 def big_sub():
12     try_sum = 0
13     try_start = 0
14     length = 0 #
15     try_length = 0 #
16   
17     start = 0
18     end = 0
19     sum = 0
20     big = loop[0]
21     big_index = 0
22   
23     for index in range(0, 2*len(loop)): #
24         i = index % len(loop) #
25   
26         if try_sum >= 0:
27             try_sum += loop[i]
28             try_length += 1 #
29             if (try_sum > sum):
30                 sum = try_sum
31                 length = try_length #
32                 if length >= len(loop): #
33                     break #
34                 end = i
35                 start = try_start
36         else: # try_sum < 0
37             try_sum = loop[i]
38             try_start = i
39             try_length = 1 #
40   
41         if loop[i] > big:
42             big = loop[i]
43             big_index = i
44   
45     if sum == 0:
46         sum = big
47         start = end = big_index
48   
49     if start <= end and length < len(loop): #
50         print loop[start:end+1],
51     elif length >= len(loop):
52         print loop,
53     else: #
54         print loop[start:],
55         print loop[:end+1],
56     print sum
57 
58 
59 big_sub()

 
注意:赤字部分は、リング配列を処理するために変更されたコードです.