貪欲法の基本原理と適用条件

貪欲法（Greedy Algorithm）は、探索空間における各段階で即時最適な選択肢を優先するアルゴリズムアプローチである。この手法は「現在利用可能な情報の中で最も効率的なパス」を逐次選択し、結果として全体最適解への収束を目指す。ただし、この方法論が常に大域的最適解を保証するわけではないため、問題構造が「貪欲選択特性」と「部分構造最適性」を同時に満たしているかの厳密な検証が必須となる。

標準的な適用フロー

1. 対象問題を相互に依存しないサブタスクに分割
2. 各ステップでの最適判断基準（グリーディポリシー）を明確化
3. 分解された部分問題に対する最適応答を逐次算出
4. 累積された局部最適解を統合し、最終的な解空間へ帰納

代表的な実装ケーススタディ

1. 資源割当問題（Assign Cookies）

要求強度（g）と利用可能なリソースサイズ（s）の双方を昇順整列させ、最小の要求から順に適合可能な最小リソースを割り当てる構成にする。これにより断片的な資源の浪費を防ぎ、満たすべき要件の総数を最大化する。

class Solution {
    public int assignCookies(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        
        int fulfilledRequirements = 0;
        int resourceCursor = 0;
        
        while (resourceCursor < s.length && fulfilledRequirements < g.length) {
            if (s[resourceCursor] >= g[fulfilledRequirements]) {
                fulfilledRequirements++;
            }
            resourceCursor++;
        }
        return fulfilledRequirements;
    }
}

2. 振動部分列の最大長（Wiggle Subsequence）

数列の隣接要素差分の符号推移を監視し、極大点と極小点が交互に出現するまでの遷移回数を計測する。同方向への連続増減區間は単一の変化点として扱い、符号が転換した瞬間のみインクリメントを行うロジックが効率良い。

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length < 2) {
            return nums.length;
        }
        
        int fluctuationCount = 1;
        int previousDiff = 0;
        int currentDiff = 0;
        
        for (int i = 1; i < nums.length; i++) {
            currentDiff = nums[i] - nums[i - 1];
            
            if ((currentDiff > 0 && previousDiff <= 0) || 
                (currentDiff < 0 && previousDiff >= 0)) {
                fluctuationCount++;
                previousDiff = currentDiff;
            }
        }
        return fluctuationCount;
    }
}

3. 最大連続部分和（Maximum Subarray）

累積スコアが負値に陥ると、その後の要素追加は全体の最大値を相対的に劣化させる。そのため、累積値が減少傾向に転じた時点で一旦初期化し、新規要素からの再計算をトリガーする構造が有効である。

class Solution {
    public int maxSubArray(int[] nums) {
        int globalMax = Integer.MIN_VALUE;
        int runningTotal = 0;
        
        for (int value : nums) {
            if (runningTotal < 0) {
                runningTotal = value;
            } else {
                runningTotal += value;
            }
            if (runningTotal > globalMax) {
                globalMax = runningTotal;
            }
        }
        return globalMax;
    }
}

4. 複数回取引による最大化（Best Time to Buy and Sell Stock II）

取引回数の制限がない環境では、長期保持による総利回りは「連日の正味の増加分を合計する」ことと数学的に同等になる。価格下落日にはポジションを持たない（差益をスキップ）ことで、すべての上昇トレンドを網羅できる。

class Solution {
    public int maxProfit(int[] prices) {
        int cumulativeYield = 0;
        
        for (int idx = 1; idx < prices.length; idx++) {
            int dailySpread = prices[idx] - prices[idx - 1];
            if (dailySpread > 0) {
                cumulativeYield += dailySpread;
            }
        }
        return cumulativeYield;
    }
}

5. 遷移可能性の判定（Jump Game）

各頂点から到達可能な範囲の右端限界（reachLimit）を追跡する。現在地が到達圏内にあれば上限を更新し続け、最終ターゲット位置に達する距離まで境界が拡張されれば真偽値を肯定する。到達不能領域に踏み入れた場合は早期終了する。

class Solution {
    public boolean canJump(int[] nums) {
        int reachLimit = 0;
        
        for (int pos = 0; pos < nums.length; pos++) {
            if (pos > reachLimit) {
                return false;
            }
            int potentialReach = pos + nums[pos];
            if (potentialReach > reachLimit) {
                reachLimit = potentialReach;
            }
            if (reachLimit >= nums.length - 1) {
                return true;
            }
        }
        return true;
    }
}

6. 最小ステップ数導出（Jump Game II）

現在の跳跃範囲内部で、次のフェーズにおいて最も遠方へ到達可能な遷移元を選択する。境界ラインに到達する度に操作回数をカウントアップし、範囲を前方へ更新し続けることで貪欲な最小移動コストを実現する。

class Solution {
    public int jump(int[] nums) {
        int boundaryEnd = 0;
        int furthestReach = 0;
        int operationCount = 0;
        
        for (int current = 0; current < nums.length - 1; current++) {
            furthestReach = Math.max(furthestReach, current + nums[current]);
            
            if (current == boundaryEnd) {
                operationCount++;
                boundaryEnd = furthestReach;
                
                if (boundaryEnd >= nums.length - 1) {
                    break;
                }
            }
        }
        return operationCount;
    }
}