יול.25

המשך ההולך וגדל ביותר

המשך ההולך וגדל ביותר

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

  1. //Time O(N^2)
  2. public static List<int> LongestIncreasingSubsequence(int[] array) {
  3. int[] sequences = new int[array.Length];
  4. Array.Fill(sequences, Int32.MinValue);
  5. int[] lengths = new int[array.Length];
  6. Array.Fill(lengths, 1);
  7. int maxLengthIndex = 0;
  8. for(int i = 0; i < array.Length; i++) {
  9. int current = array[i];
  10. for(int j = 0; j < i; j++) {
  11. int other = array[j];
  12. if(other < current && lengths[j] + 1 > lengths[i]) {
  13. lengths[i] = lengths[j] + 1;
  14. sequences[i] = j;
  15. }
  16. }
  17. if(lengths[i] >= lengths[maxLengthIndex])
  18. maxLengthIndex = i;
  19. }
  20. return buildResult(array, sequences, maxLengthIndex);
  21. }
  22. public static List<int> buildResult(int[] array, int[] sequences, int currentIndex) {
  23. List<int> result = new List<int>();
  24. while(currentIndex != Int32.MinValue) {
  25. result.Insert(0, array[currentIndex]);
  26. currentIndex = sequences[currentIndex];
  27. }
  28. return result;
  29. }


תגיות:
שתף את הסיפור הזה:

תגובות(0)

השאירו תגובה

קפטצ'ה לא מתאימה

תגובה