Znajdowanie rosnących podciągów pierwszych

Jest dane zadanie: Mamy tablicę [1..max,1..max]. Napisz funkcję, która zwraca długość najdłuższego podciągu rosnącego
znajdującego się w dowolnym (jednym) wierszu, którego wszystkie elementy są ze sobą względnie
pierwsze.

#include<iostream>
using namespace std;
const int MAX = 5; 



void wypisz(int tab[][MAX])
{
	for(int y=0;y<MAX;y++)
	{
		for(int x=0;x<MAX;x++)
			cout<<tab[y][x]<<" ";
	cout<<endl;
	
	}
}
bool wzglp(int a, int b)
{
	int c;
	
	while(b!=0)
	{
		c=a%b;
		a=b;
		b=c;
	}
	
	if(a==1)
		return true;
	return false; 
}

int najdluzszy(int tab[][MAX], int pozx,int pozy, int gleb, int iloczyn)
{
	
	int m=0;
	int t=0;
	
	
	for(int npozx=pozx+1;npozx<MAX;npozx++)
	{
		
		if(tab[pozy][npozx]>tab[pozy][pozx] && wzglp(tab[pozy][npozx],iloczyn)==1)
			t=najdluzszy(tab,npozx,pozy,gleb+1,iloczyn*tab[pozy][npozx]);
		if(t>m)
			m=t;
	}
	if(gleb>m)
		return gleb;
	return m;
		
}
int wiersze(int tab[][MAX])
{
	int m=0;
	int t=0;
	for(int y=0;y<MAX;y++)
	{
		t=najdluzszy(tab,0,y,1,1);
		if(t>m)
			m=t;
	}
	
	return m;
	
}

int main()
{
	int tab[MAX][MAX];
	
	for(int y=0;y<MAX;y++)
		for(int x=0;x<MAX;x++)
			tab[y][x]=1;
			
	tab[2][0]=1;
	tab[2][1]=4;
	tab[2][2]=6;
	tab[2][3]=5;
	tab[2][4]=11;
	
	tab[1][0]=1;
	tab[1][1]=2;
	tab[1][2]=3;
	tab[1][3]=5;
	tab[1][4]=11;
	
	wypisz(tab);
	
	int m=0;
	m=wiersze(tab);
	cout<<m<<endl;
	
}

Mam do Was pytanie :)
Napisałem program rekurencyjnie i działa, lecz autor sugeruje rozwiązanie iteracyjne, czy da się sprawę sensownie rozwiązać iteracyjnie?
Czy w programie rekurencyjnym lepiej przekazywać największą wartość 'w górę' przez returny czy przez referencję? (u mnie przez returny)

Tu tak na szybko. Jedyny mankament, to nie redukowanie do postaci zasadniczej, że tak się wyrażę. Tobie pozostawiam ulepszenie, by w zmiennej iloczyn przechowywany był iloczyn unikalnych liczb pierwszych, z jakich składa się dana liczba. Chodzi o to, że teraz jak mam powiedzmy 2, 9, to zapisuję w iloczynie 18 = 2 x 3 x 3. A wystarczy 2 x 3. Tobie pozostawiam napisanie funkcji, która rozbije liczbę na czynniki pierwsze i weźmie po jednym z każdego. Bo teraz, jak zwiększysz stałą MAX, lub zwiększysz zakres to się posypie.

#include <iostream>
#include <cstdio>
#include <ctime>
#include <cstdio>

using namespace std;

const int MAX = 10;

void wypelnij(int tab[][MAX])
{
	srand(time(0));
	
	for (int i = 0; i < MAX; i++)
		for (int j = 0; j < MAX; j++)
			tab[i][j] = 1 + rand() % 10; // liczby z zakresu [1,10]
}

void wypisz(int tab[][MAX])
{
	for (int i = 0; i < MAX; i++)
	{
		for (int j = 0; j < MAX; j++)
			printf("%3d", tab[i][j]);
		
		cout << endl;
	}
}

bool wzglp(int a, int b)
{
	int c;

	while (b != 0)
	{
		c = a % b;
		a = b;
		b = c;
	}

	if (a == 1)
		return true;
	
	return false; 
}

int maxPodciag(int tab[][MAX], int & x, int & y)
{
	int maxDlugoscPodciagu = 0;
	int aktualnaDlugosc = 0;
	bool czyNowaSeria = false;
	long long iloczyn;
	
	for (int i = 0; i < MAX; i++)
		for (int j = 0; j < MAX; j++)
		{
			czyNowaSeria = false;
			
			for (int k = j; k < MAX; k++)
			{
				if (!czyNowaSeria)
				{
					czyNowaSeria = true;
					iloczyn = tab[i][k];
					aktualnaDlugosc = 1;
					
					continue;
				}
				
				if (wzglp(iloczyn, tab[i][k]) && tab[i][k] > tab[i][k - 1])
				{
					iloczyn *= tab[i][k];
					aktualnaDlugosc++;
					
					continue;
				}
				
				else
				{
					if (aktualnaDlugosc > maxDlugoscPodciagu)
					{
						maxDlugoscPodciagu = aktualnaDlugosc;
						
						x = i;
						y = j;
					}
					
					czyNowaSeria = false;
					break;
				}
			}
		}
	
	return maxDlugoscPodciagu;
}

int main()
{
	int tab[MAX][MAX];
	wypelnij(tab);
	wypisz(tab);
	
	int polozenieX, polozenieY;
	cout << endl << maxPodciag(tab, polozenieX, polozenieY) << endl;
	cout << polozenieX << " " << polozenieY << endl;
	
	return 0;
}

Zobacz

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

using tab2d = vector<vector<int>>;

int findLongestSubsequenceLength( const tab2d& table )
{
    set<int> length;
    auto isProperRelation = []( int a , int b ){ return  __gcd(a,b) == 1 && a<b; };

    for( const auto& sequence : table )
    {
        vector<int> possibly_lengths(sequence.size(),0);

        for( size_t a=0 ; a<sequence.size()-1 ; ++a )
        {
            for( size_t i=a+1 ; i<sequence.size() ; ++i )
            {
                if( isProperRelation( sequence[a],sequence[i] ) ) ++possibly_lengths[a];
                else break;
            }
        }

        for( size_t a=0 ; a<sequence.size()-1 ; ++a )
        {
            int size {1} , reduce {possibly_lengths[a]};
            for( size_t i=a+1 ; i<sequence.size() ; ++i )
            {
                if( reduce!=0 )
                {
                  if( --reduce>possibly_lengths[i] ) reduce = possibly_lengths[i];
                }
                else break;
                size = i-a+1;
            }
            length.insert(size);
        }
    }

    return (*--length.end());
}

int main()
{
    cout << findLongestSubsequenceLength( tab2d({ {1,-2,3,5,-7} , {15,9,1,12} , {1,2,3,7,11,13,20,25,30} }) ) << "\n" ;
    return 0;
}

Masz linka do zadania?
Twoje rozwiązanie jest siłowe.
Zastanawiam się, czy są jakieś dodatkowe więzy, które pozwoliły by uzyskać lepsze rozwiązanie o mniejszej złożoności obliczeniowej.

@mpaw: Pytanie, czy Twój program liczy wszystkie podciągi typu 1,2,6,3,5,1, podciąg 4 elementowy czy tylko 'podciągi zwarte' czyli 8,1,2,3,2,9? podciąg zwarty 3 elementowy