Longest Increasing Subsequence

  # ----------------------------------------
  # 4. Longest Increasing Subsequence - Classic Array DP
  #
  # Problem: Find the length of the longest strictly increasing subsequence.
  #
  # Input: [10, 9, 2, 5, 3, 7, 101, 18]
  # Output: 4 ([2, 3, 7, 18] or [2, 3, 7, 101])
  #
  # Time Complexity: O(n²)
  # Space Complexity: O(n)
  # ----------------------------------------
  def longest_increasing_subsequence(nums)
    return 0 if nums.empty?
    
    dp = Array.new(nums.length, 1)
    
    (1...nums.length).each do |i|
      (0...i).each do |j|
        if nums[j] < nums[i]
          dp[i] = [dp[i], dp[j] + 1].max
          puts "nums[#{i}]=#{nums[i]} > nums[#{j}]=#{nums[j]}, dp[#{i}] = #{dp[i]}"
        end
      end
    end
    
    result = dp.max
    puts "Longest increasing subsequence length: #{result}"
    puts "DP array: #{dp.inspect}"
    result