davegimo

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