718. 最長共通部分配列の探索

2つの整数配列が与えられた場合、最長の共通部分配列の長さを求める問題です。部分配列は連続する要素から構成され、相対的な順序を保持する必要があります。

例：

入力：
配列A: [5, 8, 3, 7, 9]
配列B: [3, 7, 9, 4, 6]
出力：3
説明：最長共通部分配列は[3, 7, 9]

解法アプローチ

2次元DPテーブルを使用します。cache[i][j]は、配列Aの0～i-1番目と配列Bの0～j-1番目の要素における最長共通部分配列の長さを表します。

状態遷移式：

• 要素が一致する場合：cache[i][j] = cache[i-1][j-1] + 1
• 一致しない場合：cache[i][j] = 0（連続性が途切れるため）

最適化実装

def find_max_common_subarray(arr1: list, arr2: list) -> int:
    len_a, len_b = len(arr1), len(arr2)
    cache = [[0] * (len_b + 1) for _ in range(len_a + 1)]
    max_length = 0
    
    for i in range(1, len_a + 1):
        for j in range(1, len_b + 1):
            if arr1[i-1] == arr2[j-1]:
                cache[i][j] = cache[i-1][j-1] + 1
                max_length = max(max_length, cache[i][j])
    return max_length

1143. 最長共通部分列の計算

2つの文字列の最長共通部分列（LCS）の長さを求める問題です。部分列は連続する必要はなく、相対的な順序を保持する必要があります。

例：

入力：
text1 = "programming"
text2 = "pragmatic"
出力：6
説明：最長共通部分列は"pragam"

状態遷移ロジック

cache[i][j]をtext1のi文字目とtext2のj文字目までのLCS長さと定義します。

遷移条件：

• 文字が一致：cache[i][j] = cache[i-1][j-1] + 1
• 不一致：cache[i][j] = max(cache[i-1][j], cache[i][j-1])

効率的な実装

def compute_lcs(str1: str, str2: str) -> int:
    m, n = len(str1), len(str2)
    prev_row = [0] * (n + 1)
    
    for i in range(1, m + 1):
        current_row = [0]
        for j in range(1, n + 1):
            if str1[i-1] == str2[j-1]:
                current_row.append(prev_row[j-1] + 1)
            else:
                current_row.append(max(prev_row[j], current_row[-1]))
        prev_row = current_row
    return prev_row[-1]

53. 最大部分和の最適化

整数配列から連続する部分配列の最大和を求める問題です。Kadaneのアルゴリズムを応用した解法が有効です。

例：

入力: [-3, 4, -1, 2, 1, -5, 4]
出力: 6
説明：部分配列[4, -1, 2, 1]の和が最大

動的計画法の適用

current_sumを現在の位置で終わる最大部分和と定義します。

更新ルール：

current_sum = max(前回のcurrent_sum + 現在の要素, 現在の要素)

空間効率の良い実装

def find_max_subarray_sum(nums: list) -> int:
    if not nums:
        return 0
        
    global_max = current_max = nums[0]
    
    for num in nums[1:]:
        current_max = max(num, current_max + num)
        global_max = max(global_max, current_max)
        
    return global_max

1035. 交差しない接続線の最大化

2つの配列間で、値が等しく交差しない線を最大限に引く問題です。本質的には最長共通部分列問題と同等です。

解法の本質

線が交差しないという制約は、要素の相対的な順序を保持する必要があることを意味します。したがって、LCSの長さがそのまま最大接続数となります。

統合的実装

def max_non_crossing_lines(seq1: list, seq2: list) -> int:
    dp_table = [[0] * (len(seq2) + 1) for _ in range(len(seq1) + 1)]
    
    for i in range(len(seq1)):
        for j in range(len(seq2)):
            if seq1[i] == seq2[j]:
                dp_table[i+1][j+1] = dp_table[i][j] + 1
            else:
                dp_table[i+1][j+1] = max(dp_table[i][j+1], dp_table[i+1][j])
                
    return dp_table[-1][-1]