fork download
copy 
  1. def optimal_subarray(A: list[int]) -> tuple[int, int, int]:
  2.     """
  3.     Finds the indices (i, j) of the contiguous subarray with the minimum sum
  4.     and returns the sum of that subarray in O(n) time using a divide-and-conquer approach.
  5.  
  6.     Args:
  7.     - A: List[int], array of integers representing the card costs.
  8.  
  9.     Returns:
  10.     - (i, j, min_sum): A tuple where i is the start index, j is the end index, and min_sum is the minimum sum.
  11.     """
  12.     # Call the recursive function to calculate the best subarray
  13.     return find_min_subarray(A, 0, len(A) - 1)
  14.  
  15.  
  16. def find_min_subarray(A: list[int], L: int, R: int) -> tuple[int, int, int, int, int, int]:
  17.     """
  18.     Recursive function to find the minimum sum subarray in A[L..R].
  19.  
  20.     Returns:
  21.     - (i, j, min_sum, total_sum, prefix_min, suffix_min)
  22.       where (i, j) are the indices of the minimum sum subarray,
  23.       min_sum is the sum of that subarray,
  24.       total_sum is the sum of the whole array A[L..R],
  25.       prefix_min is the minimum prefix sum of A[L..R],
  26.       suffix_min is the minimum suffix sum of A[L..R].
  27.     """
  28.     # Base case: only one element
  29.     if L == R:
  30.         return (L, R, A[L], A[L], A[L], A[L])
  31.  
  32.     # Divide step: Find the middle index
  33.     M = (L + R) // 2
  34.  
  35.     # Conquer step: Recursively find the minimum subarrays in the left and right halves
  36.     (i_L, j_L, min_L, total_L, prefix_L, suffix_L) = find_min_subarray(A, L, M)
  37.     (i_R, j_R, min_R, total_R, prefix_R, suffix_R) = find_min_subarray(A, M + 1, R)
  38.  
  39.     # Combine step: Calculate the crossing subarray
  40.     cross_sum = suffix_L + prefix_R
  41.  
  42.     # Determine the best crossing subarray indices
  43.     left_suffix_sum = 0
  44.     left_suffix_min = float('inf')
  45.     left_suffix_index = M
  46.     for i in range(M, L - 1, -1):
  47.         left_suffix_sum += A[i]
  48.         if left_suffix_sum < left_suffix_min:
  49.             left_suffix_min = left_suffix_sum
  50.             left_suffix_index = i
  51.  
  52.     right_prefix_sum = 0
  53.     right_prefix_min = float('inf')
  54.     right_prefix_index = M + 1
  55.     for j in range(M + 1, R + 1):
  56.         right_prefix_sum += A[j]
  57.         if right_prefix_sum < right_prefix_min:
  58.             right_prefix_min = right_prefix_sum
  59.             right_prefix_index = j
  60.  
  61.     # Cross indices and sum
  62.     i_C = left_suffix_index
  63.     j_C = right_prefix_index
  64.     min_C = cross_sum
  65.  
  66.     # Calculate total, prefix, and suffix for the combined array
  67.     total_sum = total_L + total_R
  68.     prefix_min = min(prefix_L, total_L + prefix_R)
  69.     suffix_min = min(suffix_R, total_R + suffix_L)
  70.  
  71.     # Find the best of the left, right, and cross subarrays
  72.     if min_L <= min_R and min_L <= min_C:
  73.         return (i_L, j_L, min_L, total_sum, prefix_min, suffix_min)
  74.     elif min_R <= min_L and min_R <= min_C:
  75.         return (i_R, j_R, min_R, total_sum, prefix_min, suffix_min)
  76.     else:
  77.         return (i_C, j_C, min_C, total_sum, prefix_min, suffix_min)
  78.  
  79.  
  80. # Example usage:
  81. A = [4,-10,3,-5,6,-2,-8,7,-3,5,-6,2]
  82. start_index, end_index, min_sum, _, _, _ = optimal_subarray(A)
  83. print(f"Optimal subarray is from index {start_index} to {end_index} with a minimum sum of {min_sum}.")
Success #stdin #stdout 0.11s 14156KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Optimal subarray is from index 1 to 6 with a minimum sum of -16.
https://ideone.com/0u0kMu
language:
Python 3 (python  3.12)
created:
2 days 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!