Algorithms

Member 10566089 wrote:

I have to write a program that

Member 10566089 wrote:

I can't find an algorithm that solves this problem in O(n). Do you have any idea?

int l, l_max, u_max, u;
int A[N+1] =  // array input
l_max= l =1;
u_max= u =1;


int i;
for (i=2;i<N;i++)
{
    if (A[i] >= A[u])
        u = i;
    else if (A[i] < A[l])
    {
        if (u-l > u_max-l_max)
        {
            l_max = l;
            u_max = u;
        }
        l = u = i;
    }
}
if (u-l > u_max - l_max)
{
    l_max = l;
    u_max = u;
}
printf("%d    %d", l_max,u_max);

	public static void main(String[] args) {
		int [] arr=  //input
		int N=arr.length;
		LinkedList <Subarray> subarrays=new LinkedList<Subarray> ();
		Subarray s=new Subarray();
		s.setStart(0);
		s.setEnd(0);
		for (int i=1;i<N;i++)
		{
			if (arr[i] < arr[i-1])
			{
				s.setEnd(i-1);
				subarrays.add(s);
				s=new Subarray();
				s.setStart(i);
				s.setEnd(i);
			}
		}
		s.setEnd(N-1);
		subarrays.add(s);
		Iterator<Subarray> iterator = subarrays.iterator();
		s=iterator.next();
		Subarray nxt;
		while (iterator.hasNext()) {
			nxt=iterator.next();
			if (arr[nxt.getEnd()]>=arr[s.getEnd()] && arr[s.getStart()]<=arr[nxt.getStart()])
				nxt.setStart(s.getStart());
			s=nxt;
		}
		iterator = subarrays.iterator();
		s=iterator.next();
		while (iterator.hasNext())
		{
			nxt=iterator.next();
			if ((nxt.getEnd()-nxt.getStart()) > (s.getEnd()-s.getStart())){
				s=nxt;
			}
		}
		System.out.print("+s.getStart()+""+s.getEnd());
	}
}

public static void main(String[] args) {
		int [] input=//input
		int max = input.length - 1;
		int[] aux = new int[input.length];	//Array con i valori massimi
		for(int i = input.length; i>0; i--){
		    if(input[i-1] > input[max])
		    {
		        max = i - 1;
		    }
		    aux[i-1] = max;
		}


		int l = 0;
		int u = 0;
		max = 0;
		int lMax = 0;
		int uMax = 0;
		
		for (int i=0;i<aux.length;i++)
			System.out.print(aux[i]+" ");
		for(int i = 0; i< input.length; i++){

			System.out.println(""+input[i]+",l: "+l+",u: "+u);
			
			if (input[i] >= input[l] && aux[l] >= i)
			{
		        u = i;
		    }
		    else
		    {
		        if(u-l > max)
		        {
		            lMax = l;
		            uMax = u;
		            max = u-l;
		        }
		        l = i;
		        u = i;
		    }
		}
		if(u-l > max){
		    lMax = l;
		    uMax = u;
		}
		System.out.println("l "+l+" u "+u);
	}