import java.util.Arrays;

public class LongestIncreasingSubsequence {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1); // Initialize all elements in dp array to 1, as each element itself is a valid subsequence of length 1.

        int maxLength = 1; // Initialize the maximum length to 1, considering a single element as the sequence.

        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1); // If nums[i] is greater than nums[j], update the longest subsequence length ending at i.
                }
            }
            maxLength = Math.max(maxLength, dp[i]); // Update the maximum length if needed.
        }

        return maxLength;
    }

    public static void main(String[] args) {
        LongestIncreasingSubsequence lis = new LongestIncreasingSubsequence();
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        int result = lis.lengthOfLIS(nums);
        System.out.println("Length of the Longest Increasing Subsequence: " + result); // Output: 4
    }
}

import java.util.Scanner;

/* In Heaven, the seed is tall and the oak small / It's input vital 
	* "The al-Madinatian," verse 236-37 
	* tinyurl.com/17snqkfv
	* email answer to [email protected]
	**/

public class Main
{
	public static void main(String args[])
	{
		int x = 0;
		int a, c, m = 10000;
		
		Scanner in = new Scanner(System.in);
		
		System.out.println("Please enter a seed, maximum 3000000:");
		x = in.nextInt();
		
		System.out.println("Please input a number, maximum 29:");
		a = in.nextInt();
		
		System.out.println("Please input a number, maximum 999999:");
		c = in.nextInt();
		
		char menu = 'y';
		while(menu != 'n')
		{
			x = (a*x + c) % m;
			
			System.out.println("The next number is " + x + "\nWould you like another? (y/n)");
			menu = in.next().charAt(0);
		}
	}
}

//██╗  ░█████╗░███╗░░░███╗  ██████╗░░█████╗░███████╗██████╗░░█████╗░██╗░░░░░██╗░░░██╗░██████╗
//██║  ██╔══██╗████╗░████║  ██╔══██╗██╔══██╗██╔════╝██╔══██╗██╔══██╗██║░░░░░██║░░░██║██╔════╝
//██║  ███████║██╔████╔██║  ██║░░██║███████║█████╗░░██║░░██║███████║██║░░░░░██║░░░██║╚█████╗░
//██║  ██╔══██║██║╚██╔╝██║  ██║░░██║██╔══██║██╔══╝░░██║░░██║██╔══██║██║░░░░░██║░░░██║░╚═══██╗
//██║  ██║░░██║██║░╚═╝░██║  ██████╔╝██║░░██║███████╗██████╔╝██║░░██║███████╗╚██████╔╝██████╔╝
//╚═╝  ╚═╝░░╚═╝╚═╝░░░░░╚═╝  ╚═════╝░╚═╝░░╚═╝╚══════╝╚═════╝░╚═╝░░╚═╝╚══════╝░╚═════╝░╚═════╝░

import java.util.*;
 
public class HeapSortMain {
 
   public static void buildheap(int []arr) {
 
    /*
     * As last non leaf node will be at (arr.length-1)/2 
     * so we will start from this location for heapifying the elements
     * */
    for(int i=(arr.length-1)/2; i>=0; i--){
           heapify(arr,i,arr.length-1);
      }
   }
 
   public static void heapify(int[] arr, int i,int size) { 
      int left = 2*i+1;
      int right = 2*i+2;
      int max;
      if(left <= size && arr[left] > arr[i]){
         max=left;
      } else {
         max=i;
      }
 
      if(right <= size && arr[right] > arr[max]) {
         max=right;
      }
      // If max is not current node, exchange it with max of left and right child
      if(max!=i) {
         exchange(arr,i, max);
         heapify(arr, max,size);
      }
   }
 
   public static void exchange(int[] arr,int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t; 
   }
 
   public static int[] heapSort(int[] arr) {
 
      buildheap(arr);
      int sizeOfHeap=arr.length-1;
      for(int i=sizeOfHeap; i>0; i--) {
         exchange(arr,0, i);
         sizeOfHeap=sizeOfHeap-1;
         heapify(arr, 0,sizeOfHeap);
      }
      return arr;
   }
 
   public static void main(String[] args) {
      int[] arr={1,10,16,19,3,5};
      System.out.println("Before Heap Sort : ");
      System.out.println(Arrays.toString(arr));
      arr=heapSort(arr);
      System.out.println("=====================");
      System.out.println("After Heap Sort : ");
      System.out.println(Arrays.toString(arr));
   }
}

//sample code to write 100 random ints to a file, 1 per line

import java.io.PrintStream;
import java.io.IOException;
import java.io.File;

import java.util.Random;

public class WriteToFile {
    public static void main(String[] args) {
        try {
            PrintStream writer = new PrintStream(new File("randInts.txt"));
            Random r = new Random();
            final int LIMIT = 100;

            for (int i = 0; i < LIMIT; i++) {
                writer.println(r.nextInt());
            }
            writer.close();
        } catch (IOException e) {
            System.out.println("An error occured while trying to write to the file");
        }
    }
}

public static void enu2ecefCov(GMatrix ecefCov, GMatrix enuCov, LLA refLLA) {
    double lambda = refLLA.longitude;
    double phi = refLLA.latitude;
    
    GMatrix R = new GMatrix(6, 6);
    GMatrix Rt = new GMatrix(6, 6);
    GMatrix tmp1 = new GMatrix(6, 6);
    GMatrix tmp2 = new GMatrix(6, 6);
    
    R.setElement(0, 0, -Math.sin(lambda));
    R.setElement(0, 1, -Math.sin(phi)*Math.cos(lambda));
    R.setElement(0, 2, Math.cos(phi)*Math.cos(lambda));
    R.setElement(1, 0, Math.cos(lambda));
    R.setElement(1, 1, -Math.sin(phi)*Math.sin(lambda));
    R.setElement(1, 2, Math.cos(phi)*Math.sin(lambda));
    R.setElement(2, 0, 0);
    R.setElement(2, 1, Math.cos(phi));
    R.setElement(2, 2, Math.sin(phi));
    R.setElement(3, 3, -Math.sin(lambda));
    R.setElement(3, 4, -Math.sin(phi)*Math.cos(lambda));
    R.setElement(3, 5, Math.cos(phi)*Math.cos(lambda));
    R.setElement(4, 3, Math.cos(lambda));
    R.setElement(4, 4, -Math.sin(phi)*Math.sin(lambda));
    R.setElement(4, 5, Math.cos(phi)*Math.sin(lambda));
    R.setElement(5, 3, 0);
    R.setElement(5, 4, Math.cos(phi));
    R.setElement(5, 5, Math.sin(phi));

    Rt.transpose(R);
    tmp1.mul(enuCov, R);
    ecefCov.mul(Rt, tmp1);
}

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode handler = head;
        while(l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                handler.next = l1;
                l1 = l1.next;
            } else {
                handler.next = l2;
                l2 = l2.next;
            }
            handler = handler.next;
        }
        
        if (l1 != null) {
            handler.next = l1;
        } else if (l2 != null) {
            handler.next = l2;
        }
        
        return head.next;
    }
}