Longest Increasing Subsequence in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

#include<stdio.h>

int max(int a, int b) { return a > b ? a : b; }

int main() {
    int a[100], dp[100], n, res = 1;
    scanf("%d", &n);
    for(int i=0; i<n; i++) scanf("%d", &a[i]), dp[i]=1;
    for(int i=1; i<n; i++)
        for(int j=0; j<i; j++)
            if(a[i]>a[j]) dp[i]=max(dp[i],dp[j]+1);
    for(int i=0; i<n; i++) if(dp[i]>res) res=dp[i];
    printf("%d", res);
}

C Output

Input:  
6  
10 9 2 5 3 7  

Output:  
3

C++ Program

#include<iostream>
using namespace std;

int main() {
    int a[100], dp[100], n, res = 1;
    cin >> n;
    for(int i=0; i<n; i++) cin >> a[i], dp[i] = 1;
    for(int i=1; i<n; i++)
        for(int j=0; j<i; j++)
            if(a[i]>a[j]) dp[i] = max(dp[i], dp[j]+1);
    for(int i=0; i<n; i++) res = max(res, dp[i]);
    cout << res;
}

C++ Output

Input:  
8  
1 3 2 4 6 5 7 8  

Output:  
7

JAVA Program

import java.util.*;

class LIS {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), a[] = new int[n], dp[] = new int[n], res = 1;
        for(int i=0; i<n; i++) a[i] = sc.nextInt(); Arrays.fill(dp, 1);
        for(int i=1; i<n; i++)
            for(int j=0; j<i; j++)
                if(a[i]>a[j]) dp[i] = Math.max(dp[i], dp[j]+1);
        for(int i=0; i<n; i++) res = Math.max(res, dp[i]);
        System.out.print(res);
    }
}

JAVA Output

Input:  
6  
3 4 1 5 6 2  

Output:  
4

Python Program

a = list(map(int, input().split()))
dp = [1]*len(a)
for i in range(1, len(a)):
    for j in range(i):
        if a[i] > a[j]:
            dp[i] = max(dp[i], dp[j]+1)
print(max(dp))

Python Output

Input:  
5 1 6 2 7  

Output:  
4

In-Depth Learning – Complete Concept in Paragraphs

What Is the Longest Increasing Subsequence (LIS)?

The Longest Increasing Subsequence (LIS) problem is about finding a sequence of numbers from the original array (not necessarily adjacent), such that the numbers are strictly increasing, and the length of this subsequence is as large as possible.

A subsequence is formed by removing zero or more elements, without changing the order of remaining elements.

For example, from the array [10, 9, 2, 5, 3, 7, 101, 18], one valid LIS is [2, 3, 7, 101] → Length = 4

---

How the Code Works

We use Dynamic Programming for this problem:

• We maintain a dp[] array where dp[i] represents the length of the LIS ending at index i.

• We initialize all dp[i] to 1 (every number is a subsequence of itself).

• For every index i, we check all previous indices j < i, and:

  • If a[i] > a[j], then dp[i] = max(dp[i], dp[j] + 1).

• Finally, the answer is the maximum value in dp[].

---

Example

Input:
a = [10, 22, 9, 33, 21, 50, 41, 60]

Explanation:

• One possible LIS: [10, 22, 33, 50, 60]

• It skips numbers that don't help increase the sequence.

Output:
5

---

Real-Life Analogy

Think of climbing a staircase where each step must be higher than the last one, but you can skip steps. Your goal is to reach the highest number of steps you can while strictly going up.

Or imagine evaluating employee promotion history — the LIS tells us how many consistent performance milestones were hit in sequence.

---

Where and When Is It Used?

LIS logic appears in:

• Stock market analysis (finding periods of increasing prices)

• Game leveling algorithms

• Version control systems (longest compatible feature chains)

• Machine learning preprocessing (data sequence evaluation)

• Coding interviews (top 10 DP problems)

It’s a favorite among interviewers at companies like Google, Amazon, Adobe, and Microsoft.

---

Time and Space Complexity

Operation	Complexity
Time	O(n²)
Space	O(n)

There is also an O(n log n) solution using binary search + tail array, but for educational clarity, O(n²) is preferred initially.

---

Python Tip for O(n log n) Version (Advanced)

python

import bisect
a = list(map(int, input().split()))
tail = []
for num in a:
    i = bisect.bisect_left(tail, num)
    if i == len(tail): tail.append(num)
    else: tail[i] = num
print(len(tail))

This advanced method keeps only the smallest possible end elements for subsequences of each length.

---

SEO-Optimized Natural Paragraph for Ranking

Looking to find the Longest Increasing Subsequence (LIS) in C, C++, Java, or Python? This guide walks you through the classic dynamic programming approach to solving LIS using a simple 2D loop logic. The LIS problem is widely used in stock trend analysis, version tracking, and interview coding rounds. Learn how to build an increasing subsequence by comparing each element to its predecessors and updating the LIS length dynamically. With real-life examples and clear code, this tutorial is ideal for beginners mastering dynamic programming and preparing for tech interviews.