fork download
copy 
  1. """
  2.  
  3. array_size n
  4.  
  5. divide arr in 4 subarray such that
  6.  
  7. (sum[0,i-1]+sum[j,k-1]) - (sum[i,j-1]+sum[k,n-1]) :=> maximum
  8.  
  9.  
  10. Bruteforce:
  11. PreCompute : Prefix_Sum
  12. There are 3 pointers : i , j , k
  13. N Cube Iteration : O(N^3)
  14.  
  15. Optimized:
  16.  
  17. (sum[0,i-1]+sum[j,k-1]) - (sum[i,j-1]+sum[k,n-1]) :=> maximum
  18.  
  19. (sum[0,i-1]-sum[i,j-1]) + (sum[j,k-1]-sum[k,n-1]) :=> reshuffled
  20.  
  21. A: sum[0,i-1]-sum[i,j-1] => 2*PS[i-1] -   PS[j-1] 
  22.  
  23. J is second pointer and 2 subarrays does not include
  24.  
  25. B: sum[j,k-1]-sum[k,n-1] =>   SS[j]   - 2*SS[k]
  26.  
  27. J is the second pointer and remaing 3 subarray include j index
  28.  
  29. for A we need max PS[i-1] meaning prev PS
  30. for B we need min SS[k] meaning prev SS
  31.  
  32. Maximize (A + B) => Max A possible + Max B Possible
  33.  
  34. PreCompute : Prefix_Sum
  35.  
  36. Algo
  37. 1. Compute Prefix_Sum
  38. 2. Compute Suffix_sum
  39.  
  40. 3. Compute bestAPrefixSum
  41. 4. Compute bestBSuffixSum
  42.  
  43. 5. Iterate once a get max
  44.  
  45. """
  46.  
  47.  
  48. import math
  49. def main(arr):
  50.     n = len(arr)
  51.  
  52.     prefix_sum = [0]*n
  53.     for i in range(n):
  54.         prefix_sum[i] = arr[i] if i==0 else arr[i] + prefix_sum[i-1]
  55.  
  56.     suffix_sum = [0]*n
  57.     for i in range(n-1,-1,-1):
  58.         suffix_sum[i] = arr[i] if i==n-1 else arr[i] + suffix_sum[i+1]
  59.  
  60.     bestAPrefixSum = [0]*n
  61.     # TWEAK 1: Start maxi at 0 to allow an empty first subarray
  62.     maxi = 0 
  63.  
  64.     # TWEAK 2: Start j from 1, so you don't skip evaluating wall j=1
  65.     for j in range(1, n):
  66.         # Update maxi before calculating to allow i = j
  67.         maxi = max(maxi, prefix_sum[j-1])
  68.         bestAPrefixSum[j] = 2*maxi - prefix_sum[j-1]
  69.  
  70.     bestBSuffixSum = [0]*n
  71.     # TWEAK 1: Start mini at 0 to allow an empty fourth subarray
  72.     mini = 0 
  73.  
  74.     # TWEAK 2: Loop down to 0, so you don't skip evaluating wall j=n-2 or lower
  75.     for j in range(n-1, -1, -1):
  76.         # Update mini before calculating to allow k = j
  77.         mini = min(mini, suffix_sum[j] if j < n else 0)
  78.         bestBSuffixSum[j] = suffix_sum[j] - 2*mini
  79.  
  80.     # Default ans to negative infinity instead of 0 to handle negative max scores
  81.     ans = -math.inf
  82.  
  83.     for i in range(1, n):  # Evaluate valid split points
  84.         ans = max(ans, bestAPrefixSum[i] + bestBSuffixSum[i])
  85.  
  86.     return ans
  87.  
  88. print(main([1, 2, 1, -5]))
  89.  
  90.  
Success #stdin #stdout 0.07s 14172KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
9
https://ideone.com/ZIb9v1
language:
Python 3 (python  3.12)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!