Skip to content
TheChatArchiveThe Chat Archive
o1-mini-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

// Cpp program to Print Longest Increasing // Subsequence using Naive approach #include…

  1. 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

  2. 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();