如何实现Unique Sort？求解基于减半删除的最大有序数组问题

Alright, let's break down how to tackle this problem step by step. First, let's restate the rules clearly to make sure we're on the same page:

Given an unsorted array, you can repeatedly delete either the first half or second half of the current array. Keep doing this until the remaining array is fully sorted. Our goal is to find the largest possible sorted array we can get through this process.

Core Approach #

This problem boils down to a recursive divide-and-conquer task with a sorted check at each step. Since we want the largest possible sorted array, we always prioritize checking longer arrays first:

1. If the current array is already sorted, that's our best candidate for this branch—return it.
2. If not, split the array into two halves, recursively process each half (since we can only keep one half per step), then return the longer sorted array from the two results.

Key Definitions for Splitting #

When splitting the array:

• For an array of length n:
  • Left half (delete the second half): Take elements from index 0 to n//2 - 1 (e.g., for n=5, this is the first 2 elements)
  • Right half (delete the first half): Take elements from index n//2 to the end (e.g., for n=5, this is the last 3 elements)

Step-by-Step Implementation #

1. Helper Function: Check if Array is Sorted #

First, we need a simple function to verify if an array is non-decreasing (we'll assume ascending order here; adjust for descending if needed):

def is_sorted(arr):
    for i in range(len(arr) - 1):
        if arr[i] > arr[i+1]:
            return False
    return True

2. Main Recursive Function #

This function will handle the splitting and recursion:

def find_largest_sorted_subarray(arr):
    # Base case: if current array is sorted, return it
    if is_sorted(arr):
        return arr.copy()
    
    n = len(arr)
    # Edge case: single element is always sorted
    if n == 1:
        return arr.copy()
    
    # Split into two halves
    left_half = arr[:n//2]
    right_half = arr[n//2:]
    
    # Recursively process both halves
    left_result = find_largest_sorted_subarray(left_half)
    right_result = find_largest_sorted_subarray(right_half)
    
    # Return the longer sorted array; if lengths are equal, return either
    return left_result if len(left_result) >= len(right_result) else right_result

Example Usage #

Let's test this with a couple of cases:

Example 1: Mixed Unsorted Array #

test_arr = [3, 1, 4, 1, 5, 9, 2, 6]
print(find_largest_sorted_subarray(test_arr))
# Output: [5, 9] (or [2, 6], both are valid length-2 sorted arrays)

Example 2: Half-Sorted Array #

test_arr = [4, 3, 2, 1, 5, 6, 7, 8]
print(find_largest_sorted_subarray(test_arr))
# Output: [5, 6, 7, 8] (the fully sorted right half, which is the largest possible)

Time Complexity #

• Each level of recursion involves checking if an array is sorted (O(n) time)
• We split the array log₂(n) times (since each step halves the problem size)
• Total time complexity: O(n log n) — efficient enough for most practical array sizes.

内容的提问来源于stack exchange，提问作者Tushar Jha