Dynamic Programming: Knapsack & Subsequences

def can_partition(nums: list[int]) -> bool:
    """Whether `nums` (positive integers) can be split into two groups with equal sums."""
    total = sum(nums)
    if total % 2 != 0:
        return False  # An odd total can't split into two equal halves.
    target = total // 2  # Each group must sum to exactly half.
    # dp[s] = whether some subset of the numbers seen so far sums to s.
    dp = [False] * (target + 1)
    dp[0] = True  # The empty subset.
    for num in nums:
        # Backwards, as in the 0/1 knapsack, so each number is used at most once.
        for s in range(target, num - 1, -1):
            dp[s] = dp[s] or dp[s - num]
    return dp[target]


if __name__ == "__main__":
    print(can_partition([1, 5, 11, 5]))  # True
    print(can_partition([1, 2, 3, 5]))  # False (odd total)
    print(can_partition([2, 2, 3, 5]))  # False (even total, but no subset makes 6)

// Whether `nums` (positive integers) can be split into two groups with equal sums.
export function canPartition(nums: number[]): boolean {
  const total = nums.reduce((sum, num) => sum + num, 0);
  if (total % 2 !== 0) return false; // An odd total can't split into two equal halves.
  const target = total / 2; // Each group must sum to exactly half.
  // dp[s] = whether some subset of the numbers seen so far sums to s.
  const dp = new Array<boolean>(target + 1).fill(false);
  dp[0] = true; // The empty subset.
  for (const num of nums) {
    // Backwards, as in the 0/1 knapsack, so each number is used at most once.
    for (let s = target; s >= num; s--) {
      dp[s] = dp[s] || dp[s - num];
    }
  }
  return dp[target];
}

console.log(canPartition([1, 5, 11, 5])); // true
console.log(canPartition([1, 2, 3, 5])); // false (odd total)
console.log(canPartition([2, 2, 3, 5])); // false (even total, but no subset makes 6)

package main

import "fmt"

// canPartition reports whether nums (positive integers) can be split into two
// groups with equal sums.
func canPartition(nums []int) bool {
	total := 0
	for _, num := range nums {
		total += num
	}
	if total%2 != 0 {
		return false // An odd total can't split into two equal halves.
	}
	target := total / 2 // Each group must sum to exactly half.
	// dp[s] = whether some subset of the numbers seen so far sums to s.
	dp := make([]bool, target+1)
	dp[0] = true // The empty subset.
	for _, num := range nums {
		// Backwards, as in the 0/1 knapsack, so each number is used at most once.
		for s := target; s >= num; s-- {
			dp[s] = dp[s] || dp[s-num]
		}
	}
	return dp[target]
}

func main() {
	fmt.Println(canPartition([]int{1, 5, 11, 5})) // true
	fmt.Println(canPartition([]int{1, 2, 3, 5}))  // false (odd total)
	fmt.Println(canPartition([]int{2, 2, 3, 5}))  // false (even total, but no subset makes 6)
}

using System;
using System.Linq;

public class Solution
{
    // Whether nums (positive integers) can be split into two groups with equal sums.
    public static bool CanPartition(int[] nums)
    {
        int total = nums.Sum();
        if (total % 2 != 0) return false; // An odd total can't split into two equal halves.
        int target = total / 2; // Each group must sum to exactly half.
        // dp[s] = whether some subset of the numbers seen so far sums to s.
        var dp = new bool[target + 1];
        dp[0] = true; // The empty subset.
        foreach (int num in nums)
        {
            // Backwards, as in the 0/1 knapsack, so each number is used at most once.
            for (int s = target; s >= num; s--)
            {
                dp[s] = dp[s] || dp[s - num];
            }
        }
        return dp[target];
    }

    public static void Main()
    {
        Console.WriteLine(CanPartition(new[] { 1, 5, 11, 5 })); // True
        Console.WriteLine(CanPartition(new[] { 1, 2, 3, 5 })); // False (odd total)
        Console.WriteLine(CanPartition(new[] { 2, 2, 3, 5 })); // False (even total, but no subset makes 6)
    }
}

import java.util.Arrays;

public class Solution {
    // Whether nums (positive integers) can be split into two groups with equal sums.
    static boolean canPartition(int[] nums) {
        int total = Arrays.stream(nums).sum();
        if (total % 2 != 0) return false; // An odd total can't split into two equal halves.
        int target = total / 2; // Each group must sum to exactly half.
        // dp[s] = whether some subset of the numbers seen so far sums to s.
        boolean[] dp = new boolean[target + 1];
        dp[0] = true; // The empty subset.
        for (int num : nums) {
            // Backwards, as in the 0/1 knapsack, so each number is used at most once.
            for (int s = target; s >= num; s--) {
                dp[s] = dp[s] || dp[s - num];
            }
        }
        return dp[target];
    }

    public static void main(String[] args) {
        System.out.println(canPartition(new int[] {1, 5, 11, 5})); // true
        System.out.println(canPartition(new int[] {1, 2, 3, 5})); // false (odd total)
        System.out.println(canPartition(new int[] {2, 2, 3, 5})); // false (even total, but no subset makes 6)
    }
}

# Length of the longest strictly increasing subsequence of `nums`, two ways.


def lis_dp(nums: list[int]) -> int:
    """O(n^2) DP: dp[i] = length of the longest increasing subsequence ending at nums[i]."""
    dp = [1] * len(nums)  # Every element alone has length 1.
    best = 0
    for i in range(len(nums)):
        for j in range(i):
            # nums[i] can extend any increasing subsequence that ends on a smaller value.
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
        best = max(best, dp[i])  # The longest can end anywhere, not just at the last index.
    return best


def lis_tails(nums: list[int]) -> int:
    """O(n log n) patience version: tails[k] = smallest value that ends an increasing
    subsequence of length k + 1. tails stays sorted, so binary search works on it."""
    tails: list[int] = []
    for x in nums:
        # Lower bound: the first tail >= x.
        lo, hi = 0, len(tails)
        while lo < hi:
            mid = (lo + hi) // 2
            if tails[mid] < x:
                lo = mid + 1
            else:
                hi = mid
        if lo == len(tails):
            tails.append(x)  # x beats every tail: the longest grows by one.
        else:
            tails[lo] = x  # Same length, lower ending: more room for later numbers.
    return len(tails)  # The right length, though tails itself may not be a subsequence.


if __name__ == "__main__":
    # Prints 4 4, then 4 4, then 1 1.
    for nums in [[10, 9, 2, 5, 3, 7, 101, 18], [0, 1, 0, 3, 2, 3], [7, 7, 7, 7, 7, 7, 7]]:
        print(lis_dp(nums), lis_tails(nums))

// Length of the longest strictly increasing subsequence of `nums`, two ways.

// O(n^2) DP: dp[i] = length of the longest increasing subsequence ending at nums[i].
export function lisDp(nums: number[]): number {
  const dp = new Array<number>(nums.length).fill(1); // Every element alone has length 1.
  let best = 0;
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      // nums[i] can extend any increasing subsequence that ends on a smaller value.
      if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
    }
    best = Math.max(best, dp[i]); // The longest can end anywhere, not just at the last index.
  }
  return best;
}

// O(n log n) patience version: tails[k] = smallest value that ends an increasing
// subsequence of length k + 1. tails stays sorted, so binary search works on it.
export function lisTails(nums: number[]): number {
  const tails: number[] = [];
  for (const x of nums) {
    // Lower bound: the first tail >= x.
    let lo = 0;
    let hi = tails.length;
    while (lo < hi) {
      const mid = Math.floor((lo + hi) / 2);
      if (tails[mid] < x) lo = mid + 1;
      else hi = mid;
    }
    if (lo === tails.length) tails.push(x); // x beats every tail: the longest grows by one.
    else tails[lo] = x; // Same length, lower ending: more room for later numbers.
  }
  return tails.length; // The right length, though tails itself may not be a subsequence.
}

// Prints 4 4, then 4 4, then 1 1.
for (const nums of [[10, 9, 2, 5, 3, 7, 101, 18], [0, 1, 0, 3, 2, 3], [7, 7, 7, 7, 7, 7, 7]]) {
  console.log(lisDp(nums), lisTails(nums));
}

// Length of the longest strictly increasing subsequence of nums, two ways.
package main

import "fmt"

// lisDp is the O(n^2) DP: dp[i] = length of the longest increasing subsequence
// ending at nums[i].
func lisDp(nums []int) int {
	dp := make([]int, len(nums))
	best := 0
	for i := range nums {
		dp[i] = 1 // Every element alone has length 1.
		for j := 0; j < i; j++ {
			// nums[i] can extend any increasing subsequence that ends on a smaller value.
			if nums[j] < nums[i] {
				dp[i] = max(dp[i], dp[j]+1)
			}
		}
		best = max(best, dp[i]) // The longest can end anywhere, not just at the last index.
	}
	return best
}

// lisTails is the O(n log n) patience version: tails[k] = smallest value that
// ends an increasing subsequence of length k + 1. tails stays sorted, so binary
// search works on it.
func lisTails(nums []int) int {
	tails := []int{}
	for _, x := range nums {
		// Lower bound: the first tail >= x.
		lo, hi := 0, len(tails)
		for lo < hi {
			mid := (lo + hi) / 2
			if tails[mid] < x {
				lo = mid + 1
			} else {
				hi = mid
			}
		}
		if lo == len(tails) {
			tails = append(tails, x) // x beats every tail: the longest grows by one.
		} else {
			tails[lo] = x // Same length, lower ending: more room for later numbers.
		}
	}
	return len(tails) // The right length, though tails itself may not be a subsequence.
}

func main() {
	// Prints 4 4, then 4 4, then 1 1.
	for _, nums := range [][]int{{10, 9, 2, 5, 3, 7, 101, 18}, {0, 1, 0, 3, 2, 3}, {7, 7, 7, 7, 7, 7, 7}} {
		fmt.Println(lisDp(nums), lisTails(nums))
	}
}

using System;
using System.Collections.Generic;

// Length of the longest strictly increasing subsequence of nums, two ways.
public class Solution
{
    // O(n^2) DP: dp[i] = length of the longest increasing subsequence ending at nums[i].
    public static int LisDp(int[] nums)
    {
        var dp = new int[nums.Length];
        Array.Fill(dp, 1); // Every element alone has length 1.
        int best = 0;
        for (int i = 0; i < nums.Length; i++)
        {
            for (int j = 0; j < i; j++)
            {
                // nums[i] can extend any increasing subsequence that ends on a smaller value.
                if (nums[j] < nums[i]) dp[i] = Math.Max(dp[i], dp[j] + 1);
            }
            best = Math.Max(best, dp[i]); // The longest can end anywhere, not just at the last index.
        }
        return best;
    }

    // O(n log n) patience version: tails[k] = smallest value that ends an increasing
    // subsequence of length k + 1. tails stays sorted, so binary search works on it.
    public static int LisTails(int[] nums)
    {
        var tails = new List<int>();
        foreach (int x in nums)
        {
            // Lower bound: the first tail >= x.
            int lo = 0, hi = tails.Count;
            while (lo < hi)
            {
                int mid = (lo + hi) / 2;
                if (tails[mid] < x) lo = mid + 1;
                else hi = mid;
            }
            if (lo == tails.Count) tails.Add(x); // x beats every tail: the longest grows by one.
            else tails[lo] = x; // Same length, lower ending: more room for later numbers.
        }
        return tails.Count; // The right length, though tails itself may not be a subsequence.
    }

    public static void Main()
    {
        // Prints 4 4, then 4 4, then 1 1.
        var inputs = new[]
        {
            new[] { 10, 9, 2, 5, 3, 7, 101, 18 },
            new[] { 0, 1, 0, 3, 2, 3 },
            new[] { 7, 7, 7, 7, 7, 7, 7 },
        };
        foreach (var nums in inputs)
        {
            Console.WriteLine($"{LisDp(nums)} {LisTails(nums)}");
        }
    }
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// Length of the longest strictly increasing subsequence of nums, two ways.
public class Solution {
    // O(n^2) DP: dp[i] = length of the longest increasing subsequence ending at nums[i].
    static int lisDp(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1); // Every element alone has length 1.
        int best = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                // nums[i] can extend any increasing subsequence that ends on a smaller value.
                if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            best = Math.max(best, dp[i]); // The longest can end anywhere, not just at the last index.
        }
        return best;
    }

    // O(n log n) patience version: tails[k] = smallest value that ends an increasing
    // subsequence of length k + 1. tails stays sorted, so binary search works on it.
    static int lisTails(int[] nums) {
        List<Integer> tails = new ArrayList<>();
        for (int x : nums) {
            // Lower bound: the first tail >= x.
            int lo = 0, hi = tails.size();
            while (lo < hi) {
                int mid = (lo + hi) / 2;
                if (tails.get(mid) < x) lo = mid + 1;
                else hi = mid;
            }
            if (lo == tails.size()) tails.add(x); // x beats every tail: the longest grows by one.
            else tails.set(lo, x); // Same length, lower ending: more room for later numbers.
        }
        return tails.size(); // The right length, though tails itself may not be a subsequence.
    }

    public static void main(String[] args) {
        // Prints 4 4, then 4 4, then 1 1.
        int[][] inputs = {{10, 9, 2, 5, 3, 7, 101, 18}, {0, 1, 0, 3, 2, 3}, {7, 7, 7, 7, 7, 7, 7}};
        for (int[] nums : inputs) {
            System.out.println(lisDp(nums) + " " + lisTails(nums));
        }
    }
}