מריה בוטוסוב

יש למצוא תת מערך הכי גדול שגודל כל הזמן במערך הנתון.

//Time O(N^2)
public static List<int> LongestIncreasingSubsequence(int[] array) {
    int[] sequences = new int[array.Length];
    Array.Fill(sequences, Int32.MinValue);
    int[] lengths = new int[array.Length];
    Array.Fill(lengths, 1);
    int maxLengthIndex = 0;
    for(int i = 0; i < array.Length; i++) {
        int current = array[i];
        for(int j = 0; j < i; j++) {
            int other  = array[j];
            if(other < current && lengths[j] + 1 > lengths[i]) {
                lengths[i] = lengths[j] + 1;
                sequences[i] = j;
            } 
        }
        if(lengths[i] >= lengths[maxLengthIndex])
            maxLengthIndex = i;
    }
    return buildResult(array, sequences, maxLengthIndex);
}
    
public static List<int> buildResult(int[] array, int[] sequences, int currentIndex) {
    List<int> result = new List<int>();
    while(currentIndex != Int32.MinValue) {
        result.Insert(0, array[currentIndex]);
        currentIndex = sequences[currentIndex];
    }
    return result;
}