getminSum.py
· 1.1 KiB · Python
Неформатований
def getMinimumSum(arr):
n = len(arr)
if n < 3:
return -1
left_min = [None] * n
min_so_far = float('inf')
# Populate left_min
for j in range(n):
if min_so_far < arr[j]:
left_min[j] = min_so_far
else:
left_min[j] = None
if arr[j] < min_so_far:
min_so_far = arr[j]
right_min = [None] * n
min_so_far = float('inf')
# Populate right_min
for j in range(n-1, -1, -1):
if min_so_far < arr[j]:
right_min[j] = min_so_far
else:
right_min[j] = None
if arr[j] < min_so_far:
min_so_far = arr[j]
min_sum = float('inf')
for j in range(n):
if left_min[j] is not None and right_min[j] is not None:
current_sum = left_min[j] + arr[j] + right_min[j]
if current_sum < min_sum:
min_sum = current_sum
return min_sum if min_sum != float('inf') else -1
# Example Usage:
if __name__ == "__main__":
arr = [3, 4, 5, 1, 2, 3, 1]
result = getMinimumSum(arr)
print(result) # Output: 4
| 1 | |
| 2 | def getMinimumSum(arr): |
| 3 | n = len(arr) |
| 4 | if n < 3: |
| 5 | return -1 |
| 6 | |
| 7 | left_min = [None] * n |
| 8 | min_so_far = float('inf') |
| 9 | |
| 10 | # Populate left_min |
| 11 | for j in range(n): |
| 12 | if min_so_far < arr[j]: |
| 13 | left_min[j] = min_so_far |
| 14 | else: |
| 15 | left_min[j] = None |
| 16 | if arr[j] < min_so_far: |
| 17 | min_so_far = arr[j] |
| 18 | |
| 19 | right_min = [None] * n |
| 20 | min_so_far = float('inf') |
| 21 | |
| 22 | # Populate right_min |
| 23 | for j in range(n-1, -1, -1): |
| 24 | if min_so_far < arr[j]: |
| 25 | right_min[j] = min_so_far |
| 26 | else: |
| 27 | right_min[j] = None |
| 28 | if arr[j] < min_so_far: |
| 29 | min_so_far = arr[j] |
| 30 | |
| 31 | min_sum = float('inf') |
| 32 | for j in range(n): |
| 33 | if left_min[j] is not None and right_min[j] is not None: |
| 34 | current_sum = left_min[j] + arr[j] + right_min[j] |
| 35 | if current_sum < min_sum: |
| 36 | min_sum = current_sum |
| 37 | |
| 38 | return min_sum if min_sum != float('inf') else -1 |
| 39 | |
| 40 | # Example Usage: |
| 41 | if __name__ == "__main__": |
| 42 | arr = [3, 4, 5, 1, 2, 3, 1] |
| 43 | result = getMinimumSum(arr) |
| 44 | print(result) # Output: 4 |
| 45 | |
| 46 |