maximum_subarray

maximum_subarray.py

def maximum_subarray_naiive(A:list) -> list:
    max_sum = 0
    optimal_subarray = []
    
    for i in range(len(A)):
        for j in range(i, len(A)):
            current_sum = sum(A[i:j+1])
            if current_sum > max_sum:
                max_sum = current_sum
                optimal_subarray = A[i:j+1] 
    return optimal_subarray

def maximum_subarray(A:list) -> list:
    # dp[k] = max i sum(A[i:k+1])と定義すると、
    # dp[k] = max(A[k], dp[k-1] + A[k])となることを利用
    # dp[k]は配列で持つ必要はない.
    
    max_sum = 0
    optimal_subarray = []
    current_sum = 0
    start_from = 0
    for i in range(len(A)):
        current_sum = max(A[i], current_sum + A[i])
        if current_sum == A[i]:
            start_from = i
        max_sum = max(max_sum, current_sum)
        if max_sum == current_sum:
            optimal_subarray = A[start_from:i+1]
    return optimal_subarray


if __name__ == '__main__':
    import random
    
    test_num = 100
    
    time_sum_naive = 0
    time_sum_dp = 0
    import time
    
    for i in range(test_num):
        test_len = random.randint(1, 100)
        test_range = random.randint(0, 1000)
        A = [random.randint(-test_range, test_range) for _ in range(test_len)]
        
        start = time.time()
        naive_result = maximum_subarray_naiive(A)
        time_sum_naive += time.time() - start
        
        start = time.time()
        dp_result = maximum_subarray(A)
        time_sum_dp += time.time() - start
        
        assert sum(naive_result) == sum(dp_result)
    
    print("All tests passed")
    print("Naive time: ", time_sum_naive / test_num)
    print("DP time: ", time_sum_dp / test_num)

国際コース2022 F2-1 Q2