how can we do n nested for loops where n is dynamic

Question

I have read the following questions but have not found a solution to my problem:

• c++ : dynamic number of nested for loops (without recursion)
• variable nested for loops

actual problem statement is :-

Job and Jimmy both are playing with numbers. Job gives Jimmy an array of numbers and asks him to tell the minimum possible last number of a non decreasing sequence of length L.

Input Format

First input line consists of a number which is size of array N.

Next line contains N space separated elements of array.

Next line contains length of the non decreasing sequence i.e. L.

Output Format

You have to print the minimum possible last number of a sequence and if their is no non-decreasing sequence of length L, then print -1

Sample Input

7
9 7 2 5 4 11 12
3

Sample Output

11

Explanation

In sample input, possible non-decreasing sequences of length L=3 are (9,11,12) , (7,11,12) , (2,5,11) , (2,4,11) , (2,5,12) , (2,4,12) , (2,11,12) , (5,11,12) , (4,11,12) and the minimum last number is 11 for the sequences (2,5,11) and (2,4,11). Hence, the answer is 11."

my code...

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int fact(int y,int x)
    {
    static int temp=0;
    if(temp==x)
    {
        temp=0;
        return 1;
    }
    else
        {
        ++temp;
        return y*fact((y-1),x);
    }
}

int main() {
    int num,randmax,n,s,q,w last=-1, minlast=-1;
    
    cin>>n;
    vector<int> a(n);
    
    for(int i=0;i<n; i++)
        {
        cin>>a[i];
    }
    cin>>s;
    vector<vector<int>> c;
    q=fact(s);
    c.resize(q);
    for(int i = 0 ; i < q ; ++i)
    {
        //Grow Columns by n
        a[i].resize(s);
    }
    w=q;
    randmax=n-1;
    int k=0;
    while(w)
        {
        for(int i=0 ; i<n ; i++){
            
        }
        num=rand()%randmax; // this works perfect as expected
        c[][i]=a[num];
        }
        w--;
    }
    /*for(int i=0;i<n;i++)
        {
        for(int j=i+1;j<n;j++)
            {
            for(int k=j+1;k<n; k++)
                {
                    if((a[i]<=a[j])&&(a[j]<=a[k]))
                        {
                        last=a[k];
                        
                        if(minlast=-1)
                        {
                            minlast=a[k];
                        }
                        if(last<minlast){
                            minlast=last;
                        }
                    }
            }
        }
    }
    */
    cout<<last;
    return 0;
}

`

I would tell you what I tried to do... I thought of mapping the data by having them randomly assigned in one of my array and then computing them..

I got lost somewhere in my code...plz gimme an solution to it...and more imp. a good explanation of the same as I got stuck at times when I need a dynamic nested n loop type of thing...

also it would be more helpful if you edit in my code or algo so that I could learn where my mistakes are there...

Thanks in advance for you time...

Answer 1

As the answers your links have pointed out, you can imitate a dynamic amount of for loops by using an array David gives a fine implementation here.

For the actual problem you gave though, I see no need for a dynamic amount of for loops at all. The problem is a standard non-decreasing subsequence problem with a slight variation.

#include <iostream>
#include <fstream>

int N, L;
int arr[100], seq[100];
int bst;

int main() {
    std::ifstream file ("c.txt");

    file >> N;
    for(int n = 0; n < N; ++n)
        file >> arr[n];
    file >> L;
    file.close();

    bst = 1e9;
    for(int i = 0; i <= N; ++i) seq[i] = 1e9;
    for(int i = 0; i < N; ++i)
    {
        int x = 0;
        while(seq[x] < arr[i]) ++x;
        seq[x] = arr[i];
        if(x + 1 >= L) 
            bst = std::min(bst, arr[i]);
    }

    std::cout << bst << std::endl;

    return 0;
}

This code should solve your problem. The first part does standard parsing and initialization. The rest is a variation on the LIS problem, which has several standard algorithms that solve it. Here, we just check that whenever we extend an array of length L or longer, we see if the element is smaller than our current.