Нахождение неубывающего непрерывного подмассива

Рассмотрим массив A[1..n] случайной длины и случайных положительных целых чисел. Мы определяем подмассив A как непрерывный сегмент A. Мы обозначаем подмассив от позиции k до позиции l (включая обе) как A[k..l]. Подмассив A[k..l] является восхождением, если A[j] ≤ A[j + 1] для всех j, где k ≤ j ‹ l. Другими словами, подъем — это неубывающий отрезок A. Вычислите максимальную длину подъема в A. Например, задан массив A =[5; 3; 6; 4; 6; 6; 7; 5], ваш алгоритм должен отображать: Максимальная длина подъема будет 4, а A[4..7] = [4; 6; 6; 7] — самый длинный подъем в массиве A. Алгоритм не может использовать какое-либо вспомогательное хранилище, такое как «дополнительные» массивы. чтобы выполнить то, что нужно. Я не уверен, как это решить, это самое близкое, что я нашел для решения.

class practice {
    public static void ascentLength(int arr[], int size) {
        int length = 0;
        int index = 0;
        for (int i = 0; i < size - 1; i++) {
            index = i;
            if (arr[0] <= arr[i + 1]) {
                System.out.println(arr[i]);
                length++;
            }
            if (arr[0] >= arr[i + 1]) {
                length = 0;
            }
        }
        System.out.println("length: " + length);
    }

    /* Driver program to test above function */
    public static void main(String[] args) {
        int arr[] = {5, 3, 6, 4, 6, 6, 7, 5};
        int n = arr.length;
        ascentLength(arr, n);
    }
}

java arrays sub-array contiguous
person some_cs_student    schedule 02.02.2021    source источник

Ответы (3)


arrow_upward
0
arrow_downward

Есть пара ошибок, которые сразу замечаю.

Внутри выражения if вы всегда сравниваете первый элемент массива со следующим элементом. Это должно быть сравнение между текущим и следующим элементом массива.

Переменная count нигде не объявлена. Каково назначение переменной count?

Во втором блоке if вы не сохраняете длину в отдельной переменной перед тем, как присвоить ей нулевое значение.

person Atul Anand    schedule 02.02.2021

arrow_upward
0
arrow_downward

Tracing код и рисунок figures для массива — хороший способ понять, что делает ваша программа.

int arr[] = {5, 3, 6, 4, 6, 6, 7, 5};

int maxLength = 0, count = 0;
for(int i = 0; i < arr.length - 1; i++){
    if(arr[i + 1] < arr[i]){
        count = 0;
    }else{
        count++;
        if(count > maxLength){
            maxLength = count;
        }
    }
}
System.out.println(maxLength + 1);

наконец, добавляется 1, потому что мы не можем compare присвоить ему число.

person XO56    schedule 02.02.2021
comment
что ты имеешь в виду под it does not print the array? Вы хотите напечатать подмассив arr, который имеет самый длинный неубывающий порядок? однако программа напечатает 4 вместо допустимого arr = {4,6,6,7}. - person XO56; 04.02.2021

arrow_upward
0
arrow_downward

Вам нужно отслеживать размер текущего всплытия и самого длинного всплытия с переменными разделения. На данной итерации вы либо начинаете новое восхождение, либо продолжаете существующее. Чтобы упростить итерацию, мы можем заранее обработать несколько особых случаев (например, массив с нулевым значением, пустой или одноэлементный).

public int maxAscentLength(int[] arr) {
  if (arr == null || arr.length == 0) {
    return 0;
  }
  if (arr.length == 1) {
    return 1;
  }
  // the largest ascent so far
  int maxLength = 0;
  // length of current ascent - init 1 because 1st element is assumed
  int currLength = 1;
  // start iteration from 1 rather than 0 because 1st element is assumed
  for (int index = 1 ; index < arr.length ; index++) {
    if (arr[index-1] <= arr[index]) {
      // continue ascent
      ++currLength;
    } else {
      // end ascent
      maxLength = Math.max(maxLength, currLength);
      currLength = 1;
    }
  }
  return Math.max(maxLength, currLength);
}
person vsfDawg    schedule 02.02.2021