// Cpp program to Print Longest Increasing // Subsequence using Naive approach #include…
- User
// Cpp program to Print Longest Increasing // Subsequence using Naive approach #include #include using namespace std;
// Function to construct and print Longest // Increasing Subsequence vector getLOS(vector& arr, int n) {
// L[i] - The longest increasing // sub-sequence ends with arr[i] vector<vector<int>> L(n); // L[0] is equal to arr[0] L[0].push_back(arr[0]); // Start from index 1 for (int i = 1; i < n; i++) { int lis = 1; // Do for every prev less than i for (int prev = 0; prev < i; prev++) { /* L[i] = {Max(L[prev])} + arr[i] where prev < i and arr[prev] < arr[i] */ if ((arr[i] > arr[prev]) && (lis < L[prev].size() + 1)) { // Copy the vector of prev and update lis of i L[i] = L[prev]; lis = L[prev].size() + 1; } } // L[i] ends with arr[i] L[i].push_back(arr[i]); } // L[i] now stores increasing sub-sequence // of arr[0..i] that ends with arr[i] vector<int> max = L[0]; // LIS will be max of all increasing // sub-sequences of arr for (vector<int> x : L) if (x.size() > max.size()) max = x; return max;}
int main() { vector arr = { 3, 2, 6, 4, 5, 1 }; int n = arr.size(); vector res = getLOS(arr, n); for (int x : res) cout << x << " "; return 0; }
Give me code in Python, Java, C#, JavaScript
Remember like Cpp is for C++ and at start replace Cpp with language name and then comment
without changing variable name and also do not change comments
have one line space after code when comment is written.
don’t use class if needed then name it GfG
don’t use public if not needed.
If main class is not needed don’t use it like in python and JavaScript
and In C program don’t use #define and malloc and calloc instead use simple array
- Assistant
# Python program to Print Longest Increasing # Subsequence using Naive approach from typing import List # Function to construct and print Longest # Increasing Subsequence def getLOS(arr: List[int], n: int) -> List[int]: # L[i] - The longest increasing # sub-sequence ends with arr[i] L: List[List[int]] = [[] for _ in range(n)] # L[0] is equal to arr[0] L[0].append(arr[0]) # Start from index 1 for i in range(1, n): lis = 1 # Do for every prev less than i for prev in range(0, i): # L[i] = {Max(L[prev])} + arr[i] # where prev < i and arr[prev] < arr[i] if (arr[i] > arr[prev]) and (lis < len(L[prev]) + 1): # Copy the vector of prev and update lis of i L[i] = L[prev].copy() lis = len(L[prev]) + 1 # L[i] ends with arr[i] L[i].append(arr[i]) # L[i] now stores increasing sub-sequence # of arr[0..i] that ends with arr[i] max_seq = L[0] # LIS will be max of all increasing # sub-sequences of arr for x in L: if len(x) > len(max_seq): max_seq = x return max_seq def main(): arr = [3, 2, 6, 4, 5, 1] n = len(arr) res = getLOS(arr, n) for x in res: print(x, end=' ') if __name__ == "__main__": main()// Java program to Print Longest Increasing // Subsequence using Naive approach import java.util.*; class GfG { // Function to construct and print Longest // Increasing Subsequence static List<Integer> getLOS(int[] arr, int n) { // L[i] - The longest increasing // sub-sequence ends with arr[i] List<List<Integer>> L = new ArrayList<>(n); for(int i = 0; i < n; i++) { L.add(new ArrayList<>()); } // L[0] is equal to arr[0] L.get(0).add(arr[0]); // Start from index 1 for (int i = 1; i < n; i++) { int lis = 1; // Do for every prev less than i for (int prev = 0; prev < i; prev++) { /* L[i] = {Max(L[prev])} + arr[i] where prev < i and arr[prev] < arr[i] */ if ((arr[i] > arr[prev]) && (lis < L.get(prev).size() + 1)) { // Copy the vector of prev and update lis of i L.set(i, new ArrayList<>(L.get(prev))); lis = L.get(prev).size() + 1; } } // L[i] ends with arr[i] L.get(i).add(arr[i]); } // L[i] now stores increasing sub-sequence // of arr[0..i] that ends with arr[i] List<Integer> maxSeq = L.get(0); // LIS will be max of all increasing // sub-sequences of arr for (List<Integer> x : L) if (x.size() > maxSeq.size()) maxSeq = x; return maxSeq; } public static void main(String[] args) { int[] arr = { 3, 2, 6, 4, 5, 1 }; int n = arr.length; List<Integer> res = getLOS(arr, n); for (int x : res) System.out.print(x + " "); } }// C# program to Print Longest Increasing // Subsequence using Naive approach using System; using System.Collections.Generic; class GfG { // Function to construct and print Longest // Increasing Subsequence static List<int> getLOS(List<int> arr, int n) { // L[i] - The longest increasing // sub-sequence ends with arr[i] List<List<int>> L = new List<List<int>>(n); for(int i = 0; i < n; i++) { L.Add(new List<int>()); } // L[0] is equal to arr[0] L[0].Add(arr[0]); // Start from index 1 for (int i = 1; i < n; i++) { int lis = 1; // Do for every prev less than i for (int prev = 0; prev < i; prev++) { /* L[i] = {Max(L[prev])} + arr[i] where prev < i and arr[prev] < arr[i] */ if ((arr[i] > arr[prev]) && (lis < L[prev].Count + 1)) { // Copy the vector of prev and update lis of i L[i] = new List<int>(L[prev]); lis = L[prev].Count + 1; } } // L[i] ends with arr[i] L[i].Add(arr[i]); } // L[i] now stores increasing sub-sequence // of arr[0..i] that ends with arr[i] List<int> maxSeq = L[0]; // LIS will be max of all increasing // sub-sequences of arr foreach(var x in L) if (x.Count > maxSeq.Count) maxSeq = x; return maxSeq; } static void Main(string[] args) { List<int> arr = new List<int> { 3, 2, 6, 4, 5, 1 }; int n = arr.Count; List<int> res = getLOS(arr, n); foreach(int x in res) Console.Write(x + " "); } }// JavaScript program to Print Longest Increasing // Subsequence using Naive approach function getLOS(arr, n) { // L[i] - The longest increasing // sub-sequence ends with arr[i] let L = Array.from({length: n}, () => []); // L[0] is equal to arr[0] L[0].push(arr[0]); // Start from index 1 for (let i = 1; i < n; i++) { let lis = 1; // Do for every prev less than i for (let prev = 0; prev < i; prev++) { /* L[i] = {Max(L[prev])} + arr[i] where prev < i and arr[prev] < arr[i] */ if ((arr[i] > arr[prev]) && (lis < L[prev].length + 1)) { // Copy the vector of prev and update lis of i L[i] = [...L[prev]]; lis = L[prev].length + 1; } } // L[i] ends with arr[i] L[i].push(arr[i]); } // L[i] now stores increasing sub-sequence // of arr[0..i] that ends with arr[i] let maxSeq = L[0]; // LIS will be max of all increasing // sub-sequences of arr for (let x of L) if (x.length > maxSeq.length) maxSeq = x; return maxSeq; } function main() { let arr = [3, 2, 6, 4, 5, 1]; let n = arr.length; let res = getLOS(arr, n); for (let x of res) process.stdout.write(x + " "); } main();