-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathFind_Max_Subarray
More file actions
268 lines (229 loc) · 7.79 KB
/
Find_Max_Subarray
File metadata and controls
268 lines (229 loc) · 7.79 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
*&---------------------------------------------------------------------*
*& Report Z_ALGORITHMS_FIND_MAX_SUBARRAY
*&
*&---------------------------------------------------------------------*
*&
*&
*&---------------------------------------------------------------------*
REPORT z_algorithms_find_max_subarray.
DATA:
gt_digits TYPE abadr_tab_int4.
DATA:
gv_low TYPE int4,
gv_high TYPE int4,
gv_sum TYPE int4.
INITIALIZATION.
PERFORM f_populate_data CHANGING
gt_digits.
START-OF-SELECTION.
PERFORM f_write_result USING
gt_digits
'Array'
0
0
0.
PERFORM f_find_max_subarray USING
gt_digits
1
10
CHANGING
gv_low
gv_high
gv_sum.
END-OF-SELECTION.
PERFORM f_write_result USING
gt_digits
'Maximum Subarray'
gv_low
gv_high
gv_sum.
*&---------------------------------------------------------------------*
*& Form F_POPULATE_DATA
*&---------------------------------------------------------------------*
* text
*----------------------------------------------------------------------*
* <--P_GT_DIGITS text
*----------------------------------------------------------------------*
FORM f_populate_data CHANGING ct_digits TYPE abadr_tab_int4.
DATA:
lv_int4 TYPE int4.
DO 10 TIMES.
CALL FUNCTION 'RANDOM_I4'
EXPORTING
rnd_min = -50
rnd_max = 100
IMPORTING
rnd_value = lv_int4.
APPEND lv_int4 TO ct_digits.
ENDDO.
ENDFORM. " F_POPULATE_DATA
*&---------------------------------------------------------------------*
*& Form F_WRITE_RESULT
*&---------------------------------------------------------------------*
* text
*----------------------------------------------------------------------*
* -->P_LT_DIGITS text
*----------------------------------------------------------------------*
FORM f_write_result USING
ut_digits TYPE abadr_tab_int4
uv_title TYPE string
VALUE(uv_low)
VALUE(uv_high)
VALUE(uv_sum).
DATA lv_int4 TYPE int4.
WRITE:
uv_title,
/.
IF uv_title = 'Array'.
LOOP AT ut_digits INTO lv_int4.
WRITE lv_int4.
ENDLOOP.
WRITE /.
ELSE.
WRITE:
uv_low,
uv_high,
uv_sum.
ENDIF.
ENDFORM. " F_WRITE_RESULT
*&---------------------------------------------------------------------*
*& Form F_FIND_MAX_SUBARRAY
*&---------------------------------------------------------------------*
* text
*----------------------------------------------------------------------*
* -->P_GT_DIGITS text
* -->P_1 text
* -->P_10 text
*----------------------------------------------------------------------*
FORM f_find_max_subarray USING
ut_digits TYPE abadr_tab_int4
value(uv_start)
value(uv_end)
CHANGING
cv_low TYPE int4
cv_high TYPE int4
cv_sum TYPE int4.
DATA:
lv_temp TYPE p DECIMALS 2,
lv_mid TYPE int4,
lv_mid_next TYPE int4,
lv_left_low TYPE int4,
lv_left_high TYPE int4,
lv_left_sum TYPE int4,
lv_right_low TYPE int4,
lv_right_high TYPE int4,
lv_right_sum TYPE int4,
lv_cross_low TYPE int4,
lv_cross_high TYPE int4,
lv_cross_sum TYPE int4.
IF uv_start = uv_end.
cv_low = uv_start.
cv_high = uv_end.
READ TABLE ut_digits INTO cv_sum INDEX cv_low.
ELSE.
lv_temp = FLOOR( ( uv_start + uv_end ) / 2 ).
lv_mid = lv_temp.
lv_mid_next = lv_mid + 1.
* Find left maximum subarray
PERFORM f_find_max_subarray USING
gt_digits
uv_start
lv_mid
CHANGING
lv_left_low
lv_left_high
lv_left_sum.
* Find right maximum subarray
PERFORM f_find_max_subarray USING
gt_digits
lv_mid_next
uv_end
CHANGING
lv_right_low
lv_right_high
lv_right_sum.
* Find crossing maximum subarray
PERFORM f_max_cross_subarray USING
gt_digits
uv_start
lv_mid
uv_end
CHANGING
lv_cross_low
lv_cross_high
lv_cross_sum.
IF lv_left_sum > lv_right_sum
AND lv_left_sum > lv_cross_sum.
cv_low = lv_left_low.
cv_high = lv_left_high.
cv_sum = lv_left_sum.
ELSEIF lv_right_sum > lv_left_sum
AND lv_right_sum > lv_cross_sum.
cv_low = lv_right_low.
cv_high = lv_right_high.
cv_sum = lv_right_sum.
ELSE.
cv_low = lv_cross_low.
cv_high = lv_cross_high.
cv_sum = lv_cross_sum.
ENDIF.
ENDIF.
ENDFORM. " F_FIND_MAX_SUBARRAY
*&---------------------------------------------------------------------*
*& Form F_MAX_CROSS_SUBARRAY
*&---------------------------------------------------------------------*
* text
*----------------------------------------------------------------------*
* -->P_GT_DIGITS text
* -->P_UV_START text
* -->P_LV_MID text
* -->P_UV_END text
* <--P_LV_CROSS_LOW text
* <--P_LV_CROSS_HIGH text
* <--P_LV_CROSS_SUM text
*----------------------------------------------------------------------*
FORM f_max_cross_subarray USING
ut_digits TYPE abadr_tab_int4
value(uv_start)
value(uv_mid)
value(uv_end)
CHANGING
cv_low TYPE int4
cv_high TYPE int4
cv_sum TYPE int4.
DATA:
lv_digit TYPE int4,
lv_mid_next TYPE int4,
lv_left_sum TYPE int4 VALUE -999,
lv_right_sum TYPE int4 VALUE -999,
lv_sum TYPE int4,
lv_max_left TYPE int4,
lv_max_right TYPE int4,
lv_index TYPE sy-index,
lv_counter TYPE int4.
lv_sum = 0.
lv_index = uv_mid.
lv_counter = uv_mid - uv_start + 1.
DO lv_counter TIMES.
CLEAR lv_digit.
READ TABLE ut_digits INTO lv_digit INDEX lv_index.
lv_sum = lv_sum + lv_digit.
IF lv_sum > lv_left_sum.
lv_left_sum = lv_sum.
lv_max_left = lv_index.
ENDIF.
lv_index = lv_index - 1.
ENDDO.
lv_sum = 0.
lv_mid_next = uv_mid + 1.
LOOP AT ut_digits INTO lv_digit FROM lv_mid_next TO uv_end.
lv_sum = lv_sum + lv_digit.
IF lv_sum > lv_right_sum.
lv_right_sum = lv_sum.
lv_max_right = sy-tabix.
ENDIF.
ENDLOOP.
cv_low = lv_max_left.
cv_high = lv_max_right.
cv_sum = lv_left_sum + lv_right_sum.
ENDFORM. " F_MAX_CROSS_SUBARRAY