SCTR’s PUNE INSTITUTE OF COMPUTER TECHNOLOGY
PUNE - 411043
Department of Electronics & Telecommunication Engineering
ASSESMENT YEAR: 2025-2026 CLASS: SY
SUBJECT: DATA STRUCTURES AND ALGORITHMS
EXPT No: LAB Ref: SY/2025-26/ Starting date:
Roll No: Submission date:
Title: 8. LCS & LIS implementation using dynamic programming
Design a C++ program to solve the following real-world applications using DP:
Problem 1. DNA Sequence Matching – Use LCS to find similarities between two DNA
Statement sequences.
2. Stock Market Analysis – Use LIS to determine the longest period of increasing
stock prices.
Programmer Name : Krishna Laxmikant Sawale
Batch : G-7
Note: copy code and then program output (No screen shots) for all cases here
1 . DNA Sequence Matching
Code :
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int longestCommonSubsequence(string X, string Y) {
int m = X.length();
int n = Y.length();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (X[i - 1] == Y[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
DSA_LAB_2025-26: Program input output 1
SCTR’s PUNE INSTITUTE OF COMPUTER TECHNOLOGY
PUNE - 411043
Department of Electronics & Telecommunication Engineering
ASSESMENT YEAR: 2025-2026 CLASS: SY
SUBJECT: DATA STRUCTURES AND ALGORITHMS
EXPT No: LAB Ref: SY/2025-26/ Starting date:
Roll No: Submission date:
return dp[m][n];
}
int main() {
string DNA1, DNA2;
cout << "Enter first DNA sequence: ";
cin >> DNA1;
cout << "Enter second DNA sequence: ";
cin >> DNA2;
int lcsLength = longestCommonSubsequence(DNA1, DNA2);
cout << "\nLength of Longest Common Subsequence: " << lcsLength << endl;
double similarity = (double)lcsLength / min(DNA1.length(), DNA2.length()) * 100;
cout << "Similarity between DNA sequences: " << similarity << "%\n";
return 0;
}
Output :
Enter first DNA sequence: llccc
Enter second DNA sequence: lclcc
Length of Longest Common Subsequence: 4
Similarity between DNA sequences: 80%
Enter first DNA sequence: lcccccc
Enter second DNA sequence: cllllll
Length of Longest Common Subsequence: 1
Similarity between DNA sequences: 14.2857%
2. Stock market analysis :
DSA_LAB_2025-26: Program input output 2
SCTR’s PUNE INSTITUTE OF COMPUTER TECHNOLOGY
PUNE - 411043
Department of Electronics & Telecommunication Engineering
ASSESMENT YEAR: 2025-2026 CLASS: SY
SUBJECT: DATA STRUCTURES AND ALGORITHMS
EXPT No: LAB Ref: SY/2025-26/ Starting date:
Roll No: Submission date:
Code :
#include <iostream>
#include <vector>
using namespace std;
int longestIncreasingSubsequence(vector<int>& prices) {
int n = prices.size();
vector<int> dp(n, 1);
int maxLength = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (prices[i] > prices[j])
dp[i] = max(dp[i], dp[j] + 1);
}
maxLength = max(maxLength, dp[i]);
}
return maxLength;
}
int main() {
int n;
cout << "Enter number of days: ";
cin >> n;
vector<int> prices(n);
cout << "Enter stock prices for " << n << " days:\n";
for (int i = 0; i < n; i++) cin >> prices[i];
int lis = longestIncreasingSubsequence(prices);
cout << "\nLongest period of increasing stock prices: " << lis << " days" << endl;
return 0;
}
DSA_LAB_2025-26: Program input output 3
SCTR’s PUNE INSTITUTE OF COMPUTER TECHNOLOGY
PUNE - 411043
Department of Electronics & Telecommunication Engineering
ASSESMENT YEAR: 2025-2026 CLASS: SY
SUBJECT: DATA STRUCTURES AND ALGORITHMS
EXPT No: LAB Ref: SY/2025-26/ Starting date:
Roll No: Submission date:
Output :
Enter number of days: 10
Enter stock prices for 10 days:
500
300
400
600
550
400
500
300
510
590
Longest period of increasing stock prices: 5 days
DSA_LAB_2025-26: Program input output 4
