# dave1

Feb 9th, 2021
522
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #used to find the subarray whose sum of elements
2. # is the highest - via sliding windows
3. # returns the max_sum and index of beginning of the subarray
4.
5.
6. def maxsubarray(a,size):
7.     max_sum = 0
8.     window_sum = 0
9.     window_start = 0
10.     index_win = 0
11.     n = len(a)
12.     for i in range(0,n,1):
13.         window_sum += a[i]
14.         if (i >= size - 1):
15.             if max_sum < window_sum:
16.                 max_sum = window_sum
17.                 index_win = window_start
18.
19.             window_sum -= a[window_start]
20.             window_start += 1
21.
22.     return (max_sum,index_win)
23.
24.
25.
26.
27.
28. def solution(A,K,L):
29.     N = len(A)
30.     if N == K+L:
31.         sum = 0
32.         for element in A:
33.             sum += element
34.         return sum
35.     else:
36.         first = max(K,L)
37.         second = min(K,L)
38.
39.         first_sum, index = maxsubarray(A,first)
40.         second_sum = max(maxsubarray(A[:index],second)[0],maxsubarray(A[(index + first):],second)[0])
41.
42.
43.         return (first_sum + second_sum) % 1000000007
44.
45.
46.
47. a = [6,1,4,6,3,2,7,4]
48.
49. print(solution(a,3,2))
RAW Paste Data