1/29
Loading...
🎯連続部分配列の最大和
配列から合計が最大になる連続区間を見つけます! • 配列: [-2, 1, -3, 4, -1, 2, 1, -5, 4] 例: [4, -1, 2, 1]の合計 = 6 この配列で合計が最大の連続区間は？ 核心：負の数があっても連続して足すと より大きな合計になることも!
Loading...
配列から合計が最大になる連続区間を見つけます! • 配列: [-2, 1, -3, 4, -1, 2, 1, -5, 4] 例: [4, -1, 2, 1]の合計 = 6 この配列で合計が最大の連続区間は？ 核心：負の数があっても連続して足すと より大きな合計になることも!
Kadane's Algorithmは、配列から連続部分配列の和が最大になる区間をO(n)時間で見つけるアルゴリズムです。各位置で「続けるか、新しく始めるか」を決定するだけです。