at.java (937 Bytes)

Klartext PHP und ähnliche Sprachen

public class Absteigendes_Teilstueck {


	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int max_length = 0, current_length = 1, max_start = 0, current_start = 0;
		int n = 8;
		int array[] = {9, 1, 4, 7, 4, 2, 0, 3};
		int[] subarray = new int[n];

		
		// Schleifenkosten: O(n)
		for(int i = 0; i < n-1; i++) {
			if(array[i+1] < array[i]) {
				current_length++;
				if(current_length > max_length) {
					max_start = current_start;
					max_length = current_length;
				}
			} else {
				current_length = 1;
				current_start = i+1;
			}
		}

		/* Hier wissen wir bereits Start und Länge des längsten absteigenden Teilstücks,
		 * müssen es also nur noch aus dem Array extrahieren.
		 */
		
		// Schleifenkosten: O(max_length) < O(n)
		for(int i = max_start; i < max_start + max_length; i++) {
			subarray[i] = array[i];
			// Output
			System.out.println(subarray[i]);
		}
		
		// Gesamtkosten: O(n) :)
	}