最長増加部分列（LIS）

// 最長増加部分列（LIS）を動的計画法で求める
function lis(arr) {
    const n = arr.length;
    if (n === 0) return { length: 0, lis: [] };
    
    // DPテーブルを初期化（全て1で初期化）
    const dp = Array(n).fill(1);
    const predecessor = Array(n).fill(-1);
    
    // DPテーブルを構築
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            // 増加条件を満たし、より長いLISが見つかった場合
            if (arr[j] < arr[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                predecessor[i] = j; // バックトラック用
            }
        }
    }
    
    // 最大長とその位置を見つける
    let maxLength = Math.max(...dp);
    let maxIndex = dp.indexOf(maxLength);
    
    // バックトラックでLISを構築
    const lisArray = [];
    let currentIndex = maxIndex;
    
    while (currentIndex !== -1) {
        lisArray.unshift(arr[currentIndex]);
        currentIndex = predecessor[currentIndex];
    }
    
    return {
        length: maxLength,
        lis: lisArray,
        dpTable: dp
    };
}

// 使用例
console.log(lis([10, 22, 9, 33, 21, 50, 41, 60]));
// { length: 5, lis: [10, 22, 33, 50, 60], dpTable: [1, 2, 1, 3, 3, 4, 4, 5] }

console.log(lis([3, 10, 2, 1, 20]));
// { length: 3, lis: [3, 10, 20], dpTable: [1, 2, 1, 1, 3] }

console.log(lis([1, 2, 3, 4, 5]));
// { length: 5, lis: [1, 2, 3, 4, 5], dpTable: [1, 2, 3, 4, 5] }

console.log(lis([5, 4, 3, 2, 1]));
// { length: 1, lis: [5], dpTable: [1, 1, 1, 1, 1] }

// 株価分析での応用例
function findLongestUptrend(prices) {
    const result = lis(prices);
    const uptrendRatio = (result.length / prices.length) * 100;
    
    return {
        ...result,
        uptrendRatio: uptrendRatio.toFixed(2) + "%",
        isStrongUptrend: result.length >= prices.length * 0.7
    };
}

const stockPrices = [100, 110, 95, 120, 115, 130, 125, 140];
console.log(findLongestUptrend(stockPrices));
// 最長上昇トレンドとその期間を分析

// 効率的なO(n log n)実装（二分探索使用）
function lisOptimized(arr) {
    const n = arr.length;
    if (n === 0) return { length: 0 };
    
    const tails = []; // tails[i] = 長さi+1のLISの末尾の最小値
    
    for (const num of arr) {
        // 二分探索でnumを挿入する位置を見つける
        let left = 0, right = tails.length;
        
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (tails[mid] < num) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        // 位置leftにnumを配置
        tails[left] = num;
    }
    
    return { length: tails.length };
}

console.log(lisOptimized([10, 22, 9, 33, 21, 50, 41, 60]));
// { length: 5 } - O(n log n)で高速計算