Lantern Melody Chain Length

Published at05 Jan 2026

Like9

You are given a list of melody values, and the goal is to find the length of the longest increasing subsequence.

A subsequence does not need to use neighboring elements, but it must keep the original left-to-right order. That means you may skip values, but you are not allowed to rearrange them.

For example, if melodies = [5,4,3], the answer is 1 because nothing rises, so the best subsequence is just one value. If melodies = [1,3,2,3,4], the answer is 4 because one valid increasing subsequence is [1,2,3,4].

So the task is to look through the sequence and keep the longest chain that stays strictly increasing while preserving the original order.

Example Input & Output

Example 1

Input

melodies = [5,4,3]

Output

Explanation

Since the numbers keep going down, the best chain is just one number long.

Example 2

Input

melodies = []

Output

Explanation

With no melodies, the chain length is zero.

Example 3

Input

melodies = [1,3,2,3,4]

Output

Explanation

A strong rising chain here is [1,2,3,4], which has length 4.

Algorithm Flow

Recommendation Algorithm Flow for Lantern Melody Chain Length

Solution Approach

The most direct dynamic programming idea is to let dp[i] mean the length of the longest increasing subsequence that ends exactly at index i.

Then for each position i, we look at all earlier positions j. If melodies[j] < melodies[i], then the subsequence ending at j can be extended by melodies[i].

dp[i] = 1 + max(dp[j]) for all j < i where melodies[j] < melodies[i]

If no earlier value is smaller, then dp[i] = 1 because the subsequence can start at i.

After filling the DP array, the answer is the largest value in dp. This runs in O(n^2) time and is easy to explain. There is also a faster O(n log n) approach, but the DP version is usually the clearest starting point.

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

java

import java.util.*;
class Solution {
    public int calculate_chain_length(int[] notes) {
        if (notes.length == 0) return 0;
        int[] tails = new int[notes.length];
        int len = 0;
        for (int x : notes) {
            int i = 0, j = len;
            while (i != j) {
                int m = (i + j) / 2;
                if (tails[m] < x) i = m + 1;
                else j = m;
            }
            tails[i] = x;
            if (i == len) len++;
        }
        return len;
    }
}

javascript

function calculate_chain_length(notes) {
    if (notes.length === 0) return 0;
    const tails = [];
    for (let x of notes) {
        let low = 0, high = tails.length - 1;
        let idx = tails.length;
        while (low <= high) {
            let mid = Math.floor((low + high) / 2);
            if (tails[mid] >= x) {
                idx = mid;
                high = mid - 1;
            } else low = mid + 1;
        }
        if (idx < tails.length) tails[idx] = x;
        else tails.push(x);
    }
    return tails.length;
}

php

function calculate_chain_length($notes) {
    if (empty($notes)) return 0;
    $tails = [];
    foreach ($notes as $x) {
        $low = 0; $high = count($tails) - 1;
        $idx = count($tails);
        while ($low <= $high) {
            $mid = floor(($low + $high) / 2);
            if ($tails[$mid] >= $x) {
                $idx = $mid;
                $high = $mid - 1;
            } else $low = $mid + 1;
        }
        if ($idx < count($tails)) $tails[$idx] = $x;
        else $tails[] = $x;
    }
    return count($tails);
}

python

import bisect
def calculate_chain_length(notes):
    if not notes: return 0
    tails = []
    for x in notes:
        idx = bisect.bisect_left(tails, x)
        if idx < len(tails): tails[idx] = x
        else: tails.append(x)
    return len(tails)

rust

pub fn calculate_chain_length(notes: Vec<i32>) -> i32 {
    if notes.is_empty() { return 0; }
    let mut tails = Vec::new();
    for &x in &notes {
        let idx = tails.binary_search(&x);
        match idx {
            Ok(i) => tails[i] = x,
            Err(i) => {
                if i < tails.len() { tails[i] = x; }
                else { tails.push(x); }
            }
        }
    }
    tails.len() as i32
}

typescript

function calculate_chain_length(notes: number[]): number {
    if (notes.length === 0) return 0;
    const tails: number[] = [];
    for (let x of notes) {
        let low = 0, high = tails.length - 1;
        let idx = tails.length;
        while (low <= high) {
            let mid = Math.floor((low + high) / 2);
            if (tails[mid] >= x) {
                idx = mid;
                high = mid - 1;
            } else low = mid + 1;
        }
        if (idx < tails.length) tails[idx] = x;
        else tails.push(x);
    }
    return tails.length;
}

Related Dynamic Programming Challenges

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this Challenge.

Lantern Melody Chain Length

Example Input & Output

Algorithm Flow

Solution Approach

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Dynamic Programming Challenges

Festival Coin Path Count

River Token Ways

Stair Lantern Routes

Max Vacation Profit

Max Harvest with Rest

Garden Lantern Seating Ways

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.