Maximum Subarray Algorithm Analysis

function maxSubArray(nums: number[]): number {
    // 現在の部分配列の和を追跡
    let currentSum: number = nums[0];
    // これまでに見つけた最大の部分配列の和
    let maxSum: number = nums[0];
    
    // 配列の2番目の要素から開始
    for (let i = 1; i < nums.length; i++) {
        // 現在の要素から新しく開始するか、既存の部分配列に追加するかを選択
        // より大きい値を選ぶ
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        
        // 最大和を更新
        maxSum = Math.max(maxSum, currentSum);
    }
    
    return maxSum;
}

function maxSubArrayDivideConquer(nums: number[]): number {
    function divideConquer(nums: number[], left: number, right: number): number {
        // ベースケース: 要素が1つの場合
        if (left === right) {
            return nums[left];
        }
        
        // 中点を計算（ビット演算で高速化）
        const mid: number = left + ((right - left) >> 1);
        
        // 左半分の最大部分配列の和
        const leftMax: number = divideConquer(nums, left, mid);
        
        // 右半分の最大部分配列の和
        const rightMax: number = divideConquer(nums, mid + 1, right);
        
        // 中点をまたぐ最大部分配列の和を計算
        let leftSum: number = Number.NEGATIVE_INFINITY;
        let sum: number = 0;
        for (let i = mid; i >= left; i--) {
            sum += nums[i];
            leftSum = Math.max(leftSum, sum);
        }
        
        let rightSum: number = Number.NEGATIVE_INFINITY;
        sum = 0;
        for (let i = mid + 1; i <= right; i++) {
            sum += nums[i];
            rightSum = Math.max(rightSum, sum);
        }
        
        const crossSum: number = leftSum + rightSum;
        
        // 3つの候補の中から最大値を返す
        return Math.max(leftMax, rightMax, crossSum);
    }
    
    return divideConquer(nums, 0, nums.length - 1);
}

function maxSubArrayOptimized(nums: number[]): number {
    let maxSum: number = nums[0];
    let currentSum: number = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        // Math.maxを避けて条件演算子を使用（わずかな性能向上）
        currentSum = currentSum > 0 ? currentSum + nums[i] : nums[i];
        
        // Math.maxを避けてif文を使用
        if (currentSum > maxSum) {
            maxSum = currentSum;
        }
    }
    
    return maxSum;
}