ช่วงย่อยผลรวมสูงสุดและช่วงย่อยผลคูณสูงสุด

ปัญหาอาร์เรย์ย่อยผลรวมสูงสุด

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
# Brute force: O(n^2)
max_sum = float('-inf')
for i in range(len(nums)):
    curr = 0
    for j in range(i, len(nums)):
        curr += nums[j]
        max_sum = max(max_sum, curr)
print(max_sum)  # 6

แนวคิดของอัลกอริทึมของ Kadane

def max_subarray(nums):
    max_sum = current_sum = nums[0]
    for num in nums[1:]:
        # Extend or start fresh?
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray(nums))  # 6

การติดตามการทำงานของอัลกอริทึมของ Kadane

def max_subarray_trace(nums):
    curr = max_sum = nums[0]
    for i, num in enumerate(nums[1:], 1):
        new_curr = max(num, curr + num)
        max_sum = max(max_sum, new_curr)
        print(f'i={i}, num={num}, curr: {curr}->{new_curr}, max={max_sum}')
        curr = new_curr
    return max_sum

max_subarray_trace([-2, 1, -3, 4, -1, 2, 1, -5, 4])

การคืนค่าอาร์เรย์ย่อยจริง

def max_subarray_indices(nums):
    max_sum = curr = nums[0]
    start = end = temp_start = 0
    for i in range(1, len(nums)):
        if nums[i] > curr + nums[i]:
            curr = nums[i]
            temp_start = i
        else:
            curr += nums[i]
        if curr > max_sum:
            max_sum = curr
            start, end = temp_start, i
    return max_sum, nums[start:end+1]

print(max_subarray_indices([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
# (6, [4, -1, 2, 1])

ปัญหาอาร์เรย์ย่อยผลคูณสูงสุด

nums = [2, 3, -2, 4]
# [2,3,-2,4]: products [2, 6, -12, -48]
# subarrays: [2]=2, [2,3]=6, [3]=3, etc.
# max is 6 from subarray [2,3]

nums2 = [-2, 3, -4]
# [-2]*3*[-4] = 24
# negative*negative=positive!
print('Expected:', 24)

การติดตามผลคูณทั้งค่าสูงสุดและค่าต่ำสุด

def max_product(nums):
    max_prod = min_prod = result = nums[0]
    for num in nums[1:]:
        # All three candidates for new max
        candidates = (num, max_prod * num, min_prod * num)
        max_prod, min_prod = max(candidates), min(candidates)
        result = max(result, max_prod)
    return result

print(max_product([2, 3, -2, 4]))    # 6
print(max_product([-2, 3, -4]))      # 24
print(max_product([-2, 0, -1]))      # 0
print(max_product([-2]))             # -2

เหตุใดผลคูณต่ำสุดจึงสำคัญ

def max_product_traced(nums):
    max_p = min_p = result = nums[0]
    for num in nums[1:]:
        prev_max, prev_min = max_p, min_p
        max_p = max(num, prev_max * num, prev_min * num)
        min_p = min(num, prev_max * num, prev_min * num)
        result = max(result, max_p)
        print(f'num={num}: max_p={max_p}, min_p={min_p}')
    return result

max_product_traced([-3, -10, 5])
# max_p after -10: 30 (flip!)
# max_p after 5: 150

ศูนย์จะรีเซ็ตผลคูณ

def max_product(nums):
    max_p = min_p = result = nums[0]
    for num in nums[1:]:
        cands = (num, max_p * num, min_p * num)
        max_p, min_p = max(cands), min(cands)
        result = max(result, max_p)
    return result

# Zero splits array into independent subarrays
print(max_product([3, -1, 4, 0, 2, 5, -1]))   # 10 (2*5)
print(max_product([0, 2]))                       # 2
print(max_product([-1, 0, -2]))                  # 0

ทางเลือก: การกวาดผลคูณจากซ้ายไปขวาและขวาไปซ้าย

def max_product_sweep(nums):
    result = max(nums)
    left = right = 1
    n = len(nums)
    for i in range(n):
        left *= nums[i]
        right *= nums[n - 1 - i]
        result = max(result, left, right)
        if left == 0: left = 1
        if right == 0: right = 1
    return result

print(max_product_sweep([2, 3, -2, 4]))   # 6
print(max_product_sweep([-2, 3, -4]))     # 24
print(max_product_sweep([-2, 0, -1]))     # 0

ความแตกต่างสำคัญระหว่าง Kadane กับผลคูณ

# Max Sum Subarray: O(n) time, O(1) space
def max_sum(nums):
    curr = result = nums[0]
    for n in nums[1:]:
        curr = max(n, curr + n)  # restart or extend
        result = max(result, curr)
    return result

# Max Product Subarray: O(n) time, O(1) space
def max_prod(nums):
    lo = hi = result = nums[0]
    for n in nums[1:]:
        lo, hi = min(n, lo*n, hi*n), max(n, lo*n, hi*n)
        result = max(result, hi)
    return result

print(max_sum([-2, 1, -3, 4, -1, 2, 1]))   # 6
print(max_prod([-2, 3, -4]))               # 24

ความซับซ้อนและเคล็ดลับการสัมภาษณ์

# Both run O(n) time, O(1) space
# Kadane handles: all negative (returns least negative)
# Product handles: zeros (resets naturally), negatives (tracks both extremes)

nums_all_neg = [-5, -2, -8]
print('Max sum (all neg):', max(max(nums_all_neg[0:1]),
      max(x for x in nums_all_neg)))  # -2
# Correct: return the maximum element when all are negative

ตรวจสอบความเข้าใจ

สรุปบทเรียน