Как найти наибольшую серию массива - Сайт, где вы сможете решить свои вопросы

Самостоятельно выполняю задание яндекс практикума, и на последнем задании столкнулся с проблемой.

Суть приложения:
Имеется двумерный массив данных (int [][] array = new int[12][30];): 12 месяцев и в каждом по 30 дней.
Пользователь самостоятельно вводит количество пройденных шагов по каждому дню, изначально массив заполнен нулями.
Есть цель по шагам в день (int targetStepsPerDay = 10000;) : 10 000 шагов.

Мне нужно найти максимальное количество подряд идущих дней, в течение которых количество шагов за день было выше целевого, т.е. выше 10000 шагов.

При выполнении функции на экран должно выводиться количество идущих подряд дней в каждом из которых количество шагов было больше чем целевое значение.

Пример вывода: “В 1-м месяце количество подряд идущих дней: 3 дня.”

Не представляю как это реализовать, всю голову сломал, помогите, пожалуйста, разобраться.

Код в классе main:

package com.FirstSprint;

import java.util.Scanner;

public class Main {
   
    public static void main(String[] args) {
        StepTracker stepTracker = new StepTracker(); // Создал объект на основе класса StepTracker
        Converter converter = new Converter(); // Создал объект на основе класса Converter
        Scanner scanner = new Scanner(System.in);
        printMenu(); // Меню для печати
        int userInput = scanner.nextInt();

        while (userInput != 11) {


            // Обработка разных случаев

            if (userInput == 1) {
                System.out.println("n 1 - Январь; 2 - Февраль; 3 - Март; 4 - Апрель; 5 - Май; 6 - Июнь; 7 - Июль; 8 - Август; 9 - Сентябрь; 10 - Октябрь; 11 - Ноябрь; 12 - Декабрь. n");
                System.out.print("Введите номер месяца: ");
                int month = scanner.nextInt();
                System.out.print("Введите номер дня от 1 до 30: ");
                int day = scanner.nextInt();
                System.out.print("Введите количество пройденных шагов за " + day + " день месяца: " );
                int steps = scanner.nextInt();
                stepTracker.isDailyStepsNotNegative(month, day, steps); // Новая функция которая должна заменять отрицательное кол-во шагов на 0.
                
            } else if (userInput == 2) {
                System.out.print("Введите номер месяца: "); 
                int month = scanner.nextInt();
                //stepTracker.printArray();
                stepTracker.printMonth(month);

            } else if (userInput == 3) {
                System.out.println("n Статистика за год: "); 
                stepTracker.printArray();

            } else if (userInput == 4) {
                System.out.print("nВведите номер месяца: n");
                int month = scanner.nextInt();
                stepTracker.summOfStepsPerMonth(month);

            } else if (userInput == 5) {
                System.out.println("n Стандартная цель по шагам за день = 10000 шагов.");
                System.out.println("n Установка цели по шагам:");
                System.out.println("n 1 - Январь; 2 - Февраль; 3 - Март; 4 - Апрель; 5 - Май; 6 - Июнь; 7 - Июль; 8 - Август; 9 - Сентябрь; 10 - Октябрь; 11 - Ноябрь; 12 - Декабрь. n");
                System.out.print("Введите номер месяца: ");
                int monthSt = scanner.nextInt();
                System.out.print("Введите номер дня от 1 до 30: ");
                int daySt = scanner.nextInt();
                System.out.print("Введите цель по шагам за " + daySt + " день " + monthSt + "-го месяца: " );
                int stepsSt = scanner.nextInt();
                stepTracker.changeTargetOfSteps(stepsSt);

            } else if (userInput == 6) {
                System.out.print("Введите номер месяца: ");
                int month = scanner.nextInt();
                stepTracker.maxAmountOfStepsPerMonth(month);

            } else if (userInput == 7) {
                System.out.print("Введите номер месяца: ");
                int month = scanner.nextInt();
                stepTracker.findAverage(month);

            } else if (userInput == 8) {
                System.out.print("nВведите количество шагов: ");
                int steps = scanner.nextInt();
                converter.convertSteps(steps);

            } else if (userInput == 9) {
                System.out.print("nВведите количество шагов: ");
                int steps = scanner.nextInt();
                converter.convertCalories(steps);

            } else if (userInput == 10) {
                **Здесь должна быть функция которая находит максимальное количество подряд идущих дней, в течение которых количество шагов за день было выше целевого.**

            } else if (userInput == 11) {

                // Это выход из программы

            } else {
                System.out.println("nТакой команды нет. Введите команду от 1 до 11."); // Команды будут позже

            }
            printMenu(); // Печатаем меню еще раз перед завершением предыдущего действия
            userInput = scanner.nextInt(); // Повторное считывание данных от пользователя


        }
        System.out.println("Программа завершена.");
    }

    private static void printMenu() {
        System.out.println("n Что вы хотите сделать?n");
        System.out.println("1) Ввести количество шагов за месяц и за день.");
        System.out.println("2) Напечатать статистику за месяц. ");
        System.out.println("3) Напечатать статистику за год. ");
        System.out.println("4) Узнать общее количество шагов за месяц.");
        System.out.println("5) Изменить цель по количеству шагов в день.");
        System.out.println("6) Показать максимально пройденное количество шаго в месяце");
        System.out.println("7) Показать среднее количество шагов в месяце");
        System.out.println("8) Показать пройденную дистанцию в месяце");
        System.out.println("9) Узнать количество сожженных килокалорий");
        System.out.println("10) Показать лучшую серию");
        System.out.println("11) Выйти из приложения");
        System.out.print("n Введите команду: ");


    }

Код в классе StepTracker:

package com.FirstSprint;


import java.util.Arrays;


public class StepTracker {
    int targetStepsPerDay = 10000;


    int [][] array = new int[12][30];

    public void printMonth (int month) { // Функция печатает статистику за определенный месяц

        for (int i = 0; i < array.length; i++) {

            if (month>=1 && month<=12) {
                System.out.println("nСтатистика за " + (month) + " месяц: n");
                System.out.println(Arrays.toString(array[month-1]));
                break;

            } else {
                System.out.println("Ошибка!nВведен некорректный номер месяца.n" + "Введите месяц от 1 до 12.n");
                break;
            }
        }

    }


    public void printArray () { // Функция печатает статистику за весь год
        for (int[] a: array) {
            System.out.println(Arrays.toString(a));
        }
    }


    public void isDailyStepsNotNegative(int month, int day, int steps) { // Новая функция которая должна заменять отрицательное кол-во шагов на 0.
        
        if (steps > 0) {
            array[month - 1][day - 1] = steps;
            

        } else {
            array[month - 1][day - 1] = (steps * 0);
        }
    }


    public void summOfStepsPerMonth(int month) { // Функция считает общее количество шагов за выбранный месяц.
        int sum = 0;
        for (int i = 0; i < array[month-1].length; i++) {
            sum += array[month-1][i];

        }
        System.out.println("nВ "+ month + "-м месяце вы прошли " + sum + " шагов.");


    }


    public void changeTargetOfSteps (int stepsSt) { // функция меняет стандартную цель по шагам по выбранному дню каждого месяца. 

        if (stepsSt > targetStepsPerDay) {
            targetStepsPerDay = stepsSt;
        } else if (stepsSt < targetStepsPerDay && stepsSt > 0) {
            targetStepsPerDay = stepsSt;
        } else if (stepsSt < 0) {
            System.out.println("nОшибка! Целевое количество шагов не может быть меньше 0. nВведите цифру больше 0.n");

        }
        System.out.println("Новая цель по шагам за текущий день = " + targetStepsPerDay);
    }


    public void maxAmountOfStepsPerMonth (int month) { // Функция находит максимальное количество шагов в выбранном месяце.
        int maos = 0;
        for (int i = 0; i < array[month-1].length; i++) {
            if (array[month-1][i] > maos) {
                maos = array[month-1][i];
            }

        }
        System.out.println("nМаксимальное количество шагов: " + maos);
    }


    public void findAverage (int month) { // Функция считает среднее количество шагов в месяце
        int sum = 0;
        for (int i = 0; i < array[month-1].length; i++) {
            sum += array[month-1][i];

        }
        System.out.println("nСреднее количесвто шагов в выбранном месяце: " + (float)sum / 30);
    }


    public void bestSeries() { **\Здесь должна быть функция которая находит максимальное количество подряд идущих дней, в течение которых количество шагов за день было выше целевого.**

    }

}

Понимаю что текста очень много, но без помощи со стороны я не смогу разобраться как это реализовать.

Молю о помощи!

Источник

Программирование. Задачи на массивы

к содержанию задачника

Заполнение массива

Заполнить массив нулями, кроме первого и последнего элементов, которые должны быть равны единице.
Заполнить массив нулями и единицами, при этом данные значения чередуются, начиная с нуля.
Заполнить массив последовательными нечетными числами, начиная с единицы.
Сформировать массив из элементов арифметической прогрессии с заданным первым элементом и разностью .
Сформировать возрастающий массив из четных чисел.
Сформировать убывающий массив из чисел, которые делятся на 3.
Создать массив из первых чисел Фибоначчи.
Заполнить массив заданной длины различными простыми числами. Натуральное число, большее единицы, называется простым, если оно делится только на себя и на единицу.
Создать массив, каждый элемент которого равен квадрату своего номера.
Создать массив, на четных местах в котором стоят единицы, а на нечетных местах – числа, равные остатку от деления своего номера на 5.
Создать массив, состоящий из троек подряд идущих одинаковых элементов.
Создать массив, который одинаково читается как слева направо, так и справа налево.
Сформировать массив из случайных чисел, в которых ровно две единицы, стоящие на случайных позициях.
Заполните массив случайным образом нулями и единицами так, чтобы количество единиц было больше количества нулей.
Сформировать массив из случайных целых чисел от 0 до 9 , в котором единиц от 3 до 5 и двоек больше троек.
Создайте массив, в котором количество отрицательных чисел равно количеству положительных и положительные числа расположены на случайных местах в массиве.
Заполните массив случайным образом нулями, единицами и двойками так, чтобы первая двойка в массиве встречалась раньше первой единицы, количество единиц было в точности равно суммарному количеству нулей и двоек.
Придумайте правило генерации массива заданной длины. Определите, сгенерирован ли данный массив вашим правилом или нет.

Анализ элементов массива

Определить, содержит ли массив данное число
Найти количество четных чисел в массиве.
Найти количество чисел в массиве, которые делятся на 3, но не делятся на 7.
Определите, каких чисел в массиве больше: которые делятся на первый элемент массива или которые делятся на последний элемент массива.
Найдите сумму и произведение элементов массива.
Найдите сумму четных чисел массива.
Найдите сумму нечетных чисел массива, которые не превосходят 11.
Найдите сумму чисел массива, которые расположены до первого четного числа массива. Если четных чисел в массиве нет, то найти сумму всех чисел за исключением крайних.
Найдите сумму чисел массива, которые стоят на четных местах.
Найдите сумму чисел массива, которые стоят на нечетных местах и при этом превосходят сумму крайних элементов массива.
Дан массив x из n элементов. Найдите $x_1-x_2+x_3-ldots-x_{n-1}+x_n$ .
Дан массив x из n элементов. Найдите $x_1x_n+x_2x_{n-1}+ldots+x_nx_1$ .
Дан массив x из n элементов. Найдите $x_n(x_n+x_{n-1})(x_n+x_{n-1}+x_{n-2})ldots (x_n+ldots+x_1)$ .
Найти наибольший элемент массива.
Найдите сумму наибольшего и наименьшего элементов массива.
Найдите количество элементов массива, которые отличны от наибольшего элемента не более чем на 10%.
Найдите наименьший четный элемент массива.
Среди элементов с нечетными номерами найдите наибольший элемент массива, который делится на 3.
Дан массив и число . Найдите два различных числа в массиве, сумма которых наиболее близка к .
Дан массив. Найдите два соседних элемента, сумма которых минимальна.
Дан массив. Найдите три последовательных элемента в массиве, сумма которых максимальна.
В данном массиве найдите количество чисел, соседи у которых отличаются более чем в 2 раза.
Найдите количество чисел, каждое из которых равно сумме квадратов своих соседей и при этом не является наибольшим в массиве.
Проверьте, содержит ли данный массив из чисел, все числа от до .
Проверьте, образует ли элементы массива в данном порядке арифметическую или геометрическую прогрессии.
Проверьте, является ли данный массив возрастающим или убывающим.
Найдите количество различных элементов данного массива.
Определите количество перемен знаков элементов массива.
В данном массиве найти максимальное количество одинаковых элементов.
Найти наиболее часто встречающийся элемент в массиве целых чисел.
В одномерном массиве, состоящем из n вещественных элементов, вычислите номер минимального элемента массива и сумму элементов массива, расположенных между первым и вторым отрицательными элементами.
Напишите программу, которая вводит с клавиатуры непустой массив целых чисел, и выводит число локальных максимумов (элемент является локальным максимумом, если он не имеет соседей, больших, чем он сам).
В данном массиве найдите два наименьших элемента.
Определите, есть ли в массиве повторяющиеся элементы.
В данном массиве найдите наибольшую серию подряд идущих элементов, расположенных по возрастанию.
В массиве найдите количество серий из четверок подряд идущих попарно различных элементов.
Определите, можно ли вычеркнуть из данного массива одно число так, чтобы оставшиеся числа оказались упорядоченными по возрастанию.

Преобразование массива

В массиве заменить все числа, большие данного числа, на среднее арифметическое всех чисел массива.
Дан массив. Заменить все числа, меньшие последнего элемента массива, на первый элемент.
Поменять местами наибольший и наименьший элементы массива.
Найти наибольший четный элемент массива и поменять его местами с наименьшим нечетным элементом. Если одного из таких элементов нет, то всем элементам массива присвоить значение, равное нулю.
Заменить каждый элемент массива с четным номером на соседний слева элемент.
Удалить в массиве первый и последний элементы.
Удалить в массиве все числа, которые повторяются более двух раз.
Найти в массиве все серии подряд идущих одинаковых элементов и удалить из них все элементы кроме одного.
Удалить в массиве все наибольшие элементы.
Переставить элементы массива в обратном порядке.
Дан массив из элементов. Сформировать новый массив такого же размера так, что элемент равен сумме элементов первых элементов массива до номера включительно.
В данном массиве найти все нулевые элементы и заменить их вместе с соседними элементами на 3.
Преобразовать массив таким образом, чтобы сначала располагались все элементы, модуль которых не превышает единицу, а потом – все остальные.
Даны два массива. Сформировать третий массив, состоящий из тех элементов, которые: а) присутствуют в обоих массивах; б) присутствуют только в одном из массивов.
Дан массив. Осуществите циклический сдвиг массив на k единиц вправо, если первый наименьший элемент массива расположен раньше последнего наибольшего элемента массива, и влево, если иначе.
Даны два массива. Определите, существуют ли в первом массиве такие два элемента, что их сумма равна сумме каких-либо трех элементов второго массива.
Дана упорядоченная последовательность чисел от 1 до N. Из копии данной последовательности удалили одно число, а оставшиеся перемешали. Найти удаленное число.
Дан массив, в котором количество отрицательных элементов равно количеству положительным. Поменяйте местами первый отрицательный и первый положительный, второй отрицательный и второй положительный и так далее.
Удалите в целочисленном массиве все положительные числа, которые являются палиндромами.
Дан массив. Сформировать новый массив, в котором идут сначала отрицательные элементы, затем нули, затем положительные.
Даны два массива. Определите все серии подряд идущих элементов из первого массива (серия может состоять и из одного элемента), каждая из которых совпадает с какой-нибудь серией подряд идущих элементов второго массива.
Дан массив из n элементов. Переставьте его элементы случайным образом.
В данном массиве каждый элемент равен 0, 1 или 2. Переставить элементы массива так, чтобы сначала располагались все нули, затем все единицы и, наконец, все двойки. Дополнительный массив не использовать.
Даны два упорядоченных по возрастанию массива. Образовать из этих двух массивов единый упорядоченный по возрастанию массив.
Осуществить поиск данного числа в упорядоченном по возрастанию массиве методом бинарного поиска.
Дан массив натуральных чисел. Найти наименьшее натуральное число, не представимое суммой никаких элементов массива. Сумма может состоять и из одного слагаемого, но каждый элемент массива может входить в нее только один раз.
В данном массиве найти серию подряд идущих элементов наибольшей длины, в которой первое число равно последнему, второе – предпоследнему и так далее.
Выполните сортировку массива следующими тремя способами: сортировкой выбором, сортировкой вставками, сортировкой обменом.
Дано натуральное число от 9 до . Необходимо найти минимальное число такое, что произведение цифр этого числа равно . Например, для ответ равен .
Даны координаты центров окружностей и их радиусы. Определите количество пар окружностей, которые пересекаются.
Даны два множества точек на плоскости. Выбрать три различные точки первого множества так, чтобы круг, ограниченный окружностью, проходящей через эти три точки, содержал все точки второго множества и имел минимальную площадь.
Даны два множества точек на плоскости. Выбрать четыре различные точки первого множества так, чтобы квадрат с вершинами в этих точках накрывал все точки второго множества и имел минимальную площадь.
На прямой задано n числовых интервалов. Определите, образует ли объединение этих интервалов один интервал.
Из данных n точек на плоскости определите те три, которые образуют треугольник наибольшей площади.
На данных n точек на плоскости найдите все тройки точек, которые образуют равносторонние треугольники.
Дано 3n точек на плоскости, причем никакие три из них не лежат на одной прямой. Построить множество n треугольников с вершинами в этих точках так, чтобы никакие два треугольника не пересекались и не содержали друг друга.
На плоскости задано множество из точек и прямая . Найдите максимальное расстояние между точками, лежащими по разные стороны от прямой.
Найти три треугольника с вершинами в заданном множестве точек на плоскости так, чтобы второй треугольник лежал строго внутри первого, а третий внутри второго.
Определите, образует ли последовательность из n точек на плоскости выпуклый многоугольник.
Дано n точек в трехмерном пространстве. Определите, лежат ли эти точки на одной плоскости.
Дано n точек на плоскости. Найдите круг минимального радиуса с центром в одной из точек, внутри которого и на границе находилось бы ровно m точек.
На плоскости дано точек. Определите коэффициенты прямой , проходящей через первую точку и наибольшее число остальных точек.
На плоскости дано точек. Определите коэффициенты прямой , проходящей через первую и одну из оставшихся точек так, чтобы все n точек лежали по одну сторону от этой прямой, и, быть может, на самой прямой.
По заданной последовательности целых чисел построить последовательность такую, что – это количество элементов, превосходящих , в начальном отрезке последовательности длиной .
Определить в заданной последовательности целых чисел количество чисел Фибоначчи.
Найти наименьшее общее кратное всех чисел, содержащихся в заданной последовательности натуральных чисел.
Пользователь вводит два натуральных числа, каждое из которых может состоять более чем из десяти цифр. Найдите сумма, разность и произведение данных чисел.
Определить количество повторений каждой из цифр в числе !, где – натуральное число, .
Получить все перестановки чисел . Например, при это 1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1.
Дан массив a размера n. Сформировать новый массив b того же размера по следующему правилу: элемент b_k равен среднему арифметическому элементов массива a с номерами от k до n.
Дан целочисленный массив размера n. Увеличить все четные числа, содержащиеся в массиве, на исходное значение первого четного числа. Если четные числа в массиве отсутствуют, то оставить массив без изменений.
Дан массив размера n. Заменить каждый элемент массива на среднее арифметическое этого элемента и его соседей.
Дан массив размера n. После каждого отрицательного элемента массива вставить элемент с нулевым значением.
Дано n точек (точки заданы своими координатами x, y). Среди всех точек этого множества, лежащих во второй четверти, найти точку, наиболее удаленную от начала координат. Если таких точек нет, то вывести точку с нулевыми координатами.
Даны n обыкновенных дробей (массив числителей и массив знаменателей). Выполнить их сложение и умножение.
Два многочлена заданы массивами своих коэффициентов. Найдите их сумму и произведение.
Два многочлена заданы массивами своих коэффициентов. Найдите частное и остаток от деления одного многочлена на второй.
Дан массив коэффициентов многочлена. Найдите производную -порядка этого многочлена.
По кругу расположены человек. Ведущий считает по кругу, начиная с первого, и исключает из круга каждого -го человека. Найдите номер человека, который останется последним в круге.
По кругу стоят человек. Ведущий посчитал человек по кругу, начиная с первого. При этом каждый из тех, кто участвовал в этом счете, получил по одной монете, остальные получили по две монеты. Далее человек, на котором остановился счет, отдает все свои монеты следующему по счету человеку, а сам выбывает из круга. Процесс продолжается с места остановки аналогичным образом до последнего человека в круге. Определите номер этого человека и количество монет, которые оказались у него в конце игры.
В массиве в порядке убывания заданы достоинства купюр валютной системы некоторой страны. Реализуйте выдачу заданной суммы s минимальным количеством купюр.
Из элементов массива a, состоящего из 2n элементов, получить массивы b и c следующим образом: выбрать в массиве a два наиболее близких по значению элемента, меньший из них поместить в массив b, а больший – в массив c. Исключить из рассмотрения в массиве a эти элементы и продолжить выбор из оставшихся элементов.
На большинстве Московских олимпиад каждый участник заполняет персональную карточку участника на которой указан 4(5)-значный номер карточки. Ясно, что не все числа из этого диапазона используются. Придумайте способы кодирования карточек, удовлетворяющие следующим требованиям:
1) При минимальном диапазоне возможных значений номеров в него должно умещаться максимальное число карточек, то есть не следует кодировать номера карточек десятизначными последовательностями.
2)Система кодирования должна уметь исправлять одну (две, …) ошибки в написании номера карточек (то есть если школьник ошибется в одной (двух, …) цифрах при переписывании номера карточек, то эта ошибка может быть исправлена, например, после ввода информации в компьютер).
3)Система кодирования должна быть максимально простой, например, номера карточек должны образовывать арифметическую прогрессию. Также желательно сделать максимально простым и алгоритм исправления ошибок в номере карточки.
Можете придумать и свои критерии к системе кодирования номеров карточек.
В данном массиве наименьший элемент поместить на первое место, наименьший из оставшихся – на последнее место, следующий – предпоследнее и так далее – до середины массива.
Даны два многочлена и . Определить коэффициенты многочлена .
Удалить в заданном массиве элементы так, чтобы оставшиеся образовывали возрастающую последовательность наибольшей длины.
В массиве h хранятся значения высот некоторого профиля местности (ее вертикального сечения) с постоянным шагом горизонтали. Найдите области (номера точек измерения высот), невидимые для наблюдателя, находящегося в точке h_i.
Даны результаты ежедневных измерений количества выпавших осадков. За какую из недель, считая с начала периода измерений, выпало наибольшее количество осадков?
Задан массив, состоящий из n неотрицательных чисел. Найдите в нем индекс элемента, для которого сумма элементов, стоящих до него, наименее отличается от суммы элементов, стоящих после него.
Данный массив разбить случайным образом на m фрагментов. Границы фрагментов сохранить в новый массив.
Реализовать алгоритм перестановки элементов массива a так, чтобы ни один из элементов не остался на своем месте и имел бы одинаковые вероятности занять любое из остальных мест.
Имитировать перетасовку колоды карт. Каждая перетасовка состоит из трех этапов: разбиение колоды на две подколоды, выбор в каждой подколоде части, перемешивание выбранных частей, объединение всех карт в одну колоду.
Даны n точек на плоскости – точки графика некоторой функции. Найти многочлен, график которого проходит через данные точки.
В игре следующие правила. В ряд лежат 25 монет. За ход разрешается брать одну или две рядом лежащие монеты. Проигрывает тот, кому нечего брать. Реализовать возможность игры пользователя с компьютером.
Построить множество, которое состоит из дружных чисел на интервале от 1 до 255. Дружными числами называется такая пара натуральных чисел М и N, для которых сумма всех делителей числа М (кроме самого М) равняется числу N, а сумма всех делителей числа N (кроме самого числа N) равняется числу М.
Игра начинается с числа 0. За ход можно прибавлять к имеющемуся числу любое число от 1 до 10. Выигрывает получивший число 100. Реализовать возможность игры пользователя с компьютером.
В игре следующие правила. Имеется две кучи конфет: в первой – 40, во второй – 45. За ход нужно одну кучу съесть, а другую разделить на две (не обязательно равные). Проигрывает тот, кто не может сделать ход. Реализовать возможность игры пользователя с компьютером.
На плоскости заданы n точек своими декартовыми координатами. Найти минимальный периметр многоугольника, содержащего все эти точки. Гарантируется, что искомый многоугольник имеет ненулевую площадь.
Вывести все представления натурального числа n суммой натуральных чисел. Перестановка слагаемых нового способа представления не дает.
Заданы вес e пустой копилки и вес v копилки с монетами. В копилке могут находиться монеты n видов; известны ценность p_i, каждого вида монет и вес w_i одной монеты. Найти минимальную и максимальную суммы денег, которые могут находиться в копилке.
Даны целых чисел. Расставить между ними знаки «+» и «-» так, чтобы значение получившегося выражения было равно заданному целому .
Даны координаты точек на плоскости. Данные точки последовательно соединяем. Предложите способ определения коэффициента от 0 до 1, по которому можно сказать, насколько сильно данная прямая похожа на прямую. Если коэффициент равен 1, то это строго прямая (с точностью используемых типов данных).
Многоугольник на плоскости задан целочисленными координатами своих n вершин в декартовой системе координат. Требуется найти число точек с целочисленными координатами, лежащих внутри многоугольника (не на границе). Стороны многоугольника друг с другом не соприкасаются (за исключением соседних — в вершинах) и не пересекаются.
Герой компьютерной игры, обладающий силой в 25 баллов, находится в круглом зале, из которого ведут 10 закрытых дверей. За каждой дверью героя ждет либо магический артефакт, дарующий силу от 10 до 80 баллов, либо монстр, имеющий силу от 5 до 100 баллов, с которым герою нужно сразиться. Битву выигрывает персонаж, обладающий наибольшей силой; если силы равны, побеждает герой.
1. Организовать ввод информации о том, что находится за дверями, либо заполнить ее, используя генератор случайных чисел.
2. Вывести эту самую информацию на экран в понятном табличном виде.
3. Посчитать, за сколькими дверями героя ждет смерть. Рекурсивно.
4. Вывести номера дверей в том порядке, в котором следует их открывать герою, чтобы остаться в живых, если такое возможно.

Источник

Есть задача:
Найти наибольший возрастающий срез массива.
Срезом будем считать последовательность подряд идущих элементов массива, где каждый следующий элемент больше предыдущего.
Для последовательности 1 2 3 1 2 5 7 1 2 1 2, существуют возрастающие срезы: 1 2 3, 1 2 5 7, 1 2, 1 2 вывести нужно срез 1 2 5 7
Для последовательности 1 2 3 1 2 5 1 2 7, существуют срезы 1 2 3, 1 2 5, 1 2 7 вывести нужно все срезы, так как они равной длины
Формат входных данных:
Дано натуральное число N, далее следуют N целых чисел.
Формат выходных данных:
В первой строке выведите длину максимального среза
Далее выведите содержание среза/срезов, разделяя элементы одним пробелом, каждый срез с новой строки

Sample Input 1:
7
2 1 2 3 1 5 7
Sample Output 1:
3
1 2 3
1 5 7
Sample Input 2:
5
1 2 3 4 5
Sample Output 2:
5
1 2 3 4 5
Sample Input 3:
7
1 2 1 5 1 7 1
Sample Output 3:
2
1 2
1 5
1 7

Вопрос: можно ли допилить мой код, или я двигаюсь в неправильном направлении? Направьте на путь истинный! Можно ли решить без второго массива?

Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = in.nextInt();
        }

        int count = 0;
        int count2 = 0;
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i] < array[i + 1]) {
                count++;
            }
            if (array[i] > array[i + 1]) {
                count++;
                count2 = count;
                count = 0;
            }

        }
        int length = Math.max(count + 1, count2);
        System.out.println(length);


        int count3 = 0;
        for (int i = 1; i < array.length; i++) {
                if (array[i] < array[i - 1]) {
                    System.out.print(array[i] + " ");
                }
                if (array[i] > array[i - 1]) {
                    System.out.print(array[i] + " ");
                    count3++;

                }
                if (count3 == length - 1) {
                    System.out.println();
                    count3 = 0;
                }
            }

Источник

Учитывая целочисленный массив, найдите следующий больший элемент для каждого элемента массива. Следующий больший элемент числа x первое большее число справа от x в массиве.

Другими словами, для каждого элемента A[i] в массиве A, найти элемент A[j] такой, что j > i а также A[j] > A[i] и значение j должно быть как можно меньше. Если следующий больший элемент не существует в массиве для любого элемента, рассмотрите его -1.

Например,

Input: [2, 7, 3, 5, 4, 6, 8]
Output: [7, 8, 5, 6, 6, 8, -1]

Input: [5, 4, 3, 2, 1]
Output: [-1, -1, -1, -1, -1]

Note that the next greater element for the last array element is always -1.

Потренируйтесь в этой проблеме

1. Подход грубой силы

Идея состоит в том, чтобы использовать два вложенных цикла. Внешний цикл принимает каждый элемент массива слева направо. Внутренний цикл рассматривает все элементы “справа” от элемента, выбранного внешним циклом. Завершите внутренний цикл, как только будет найден первый больший элемент, который будет следующим большим элементом для элемента, выбранного внешним циклом.

Временная сложность этого подхода составляет O(n²), куда n это размер ввода. Ниже приведена реализация на C, Java и Python, основанная на приведенной выше идее:

C

#include <stdio.h>

// Находим следующий больший элемент для каждого элемента в массиве

void findNextGreaterElements(int input[], int n)

{

// делаем для каждого элемента

for (int i = 0; i < n; i++)

{

// отслеживать следующий больший элемент для элемента `input[i]`

int next = –1;

// обрабатывать элементы справа от элемента `input[i]`

for (int j = i + 1; j < n; j++)

{

// прерываем внутренний цикл на первом большем элементе

// справа от элемента `input[i]`

if (input[j] > input[i])

{

next = input[j];

break;

}

printf(“%d “, next);

}

int main(void)

{

int input[] = { 2, 7, 3, 5, 4, 6, 8 };

int n = sizeof(input) / sizeof(input[0]);

findNextGreaterElements(input, n);

return 0;

}

Скачать Выполнить код

результат:

7 8 5 6 6 8 -1

Java

class Main

{

// Находим следующий больший элемент для каждого элемента массива

public static void findNextGreaterElements(int[] input)

{

// базовый вариант

if (input == null) {

return;

}

// делаем для каждого элемента

for (int i = 0; i < input.length; i++)

{

// отслеживать следующий больший элемент для элемента `input[i]`

int next = –1;

// обрабатывать элементы справа от элемента `input[i]`

for (int j = i + 1; j < input.length; j++)

{

// прерываем внутренний цикл на первом большем элементе

// справа от элемента `input[i]`

if (input[j] > input[i])

{

next = input[j];

break;

}

System.out.print(next + ” “);

}

public static void main(String[] args)

{

int[] input = { 2, 7, 3, 5, 4, 6, 8 };

findNextGreaterElements(input);

}

Скачать Выполнить код

результат:

7 8 5 6 6 8 -1

Python

# Найти следующий больший элемент для каждого элемента массива

def findNextGreaterElements(input):

# Базовый вариант

if not input:

return

# делаем на каждый элемент

for i in range(len(input)):

# отслеживает следующий больший элемент для элемента `input[i]`

next = –1

# Элементы процесса # справа от элемента `input[i]`

for j in range(i + 1, len(input)):

# разрывает внутренний цикл на первом большем элементе на

# справа от элемента `input[i]`

if input[j] > input[i]:

next = input[j]

break

print(next, end=‘ ‘)

if __name__ == ‘__main__’:

input = [2, 7, 3, 5, 4, 6, 8]

findNextGreaterElements(input)

Скачать Выполнить код

результат:

7 8 5 6 6 8 -1

2. Использование stack

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

Для каждого элемента x в массиве извлекать все элементы из stack меньше, чем x, и установите их следующий больший элемент равным x.
Цикл, пока у нас не будет большего элемента на вершине stack, или стек не станет пустым. Затем нажмите текущий элемент x на вершине stack.
Повторите процесс для каждого элемента массива.

Ниже приведена программа на C++, Java и Python, демонстрирующая этот алгоритм. Обратите внимание, что мы помещаем в stack индексы, а не сами элементы. Теперь для извлеченных элементов можно установить следующий больший элемент, используя их индекс.

C++

#include <iostream>

#include <stack>

#include <vector>

using namespace std;

// Находим следующий больший элемент для каждого элемента в массиве

vector<int> findNextGreaterElements(vector<int> const &input)

{

int n = input.size();

vector<int> result(n, –1);

// создаем пустой stack

stack<int> s;

// делаем для каждого элемента

for (int i = 0; i < n; i++)

{

// цикл до тех пор, пока у нас не будет большего элемента сверху или stack не станет пустым.

// Продолжайте извлекать из stack элементы меньшего размера, чем текущий

// элемент и установить их следующий больший элемент в текущий элемент

while (!s.empty() && input[s.top()] < input[i])

{

result[s.top()] = input[i];

s.pop();

}

// поместить текущий “индекс” в stack

s.push(i);

}

return result;

}

int main()

{

vector<int> input = { 2, 7, 3, 5, 4, 6, 8 };

vector<int> result = findNextGreaterElements(input);

for (int i: result) {

cout << i << ‘ ‘;

}

return 0;

}

Скачать Выполнить код

результат:

7 8 5 6 6 8 -1

Java

import java.util.Arrays;

import java.util.Stack;

class Main

{

// Находим следующий больший элемент для каждого элемента массива

public static int[] findNextGreaterElements(int[] input)

{

// базовый вариант

if (input == null) {

return input;

}

int[] result = new int[input.length];

Arrays.fill(result, –1);

// создаем пустой stack

Stack<Integer> s = new Stack<>();

// делаем для каждого элемента

for (int i = 0; i < input.length; i++)

{

// цикл до тех пор, пока у нас не будет большего элемента сверху или stack не станет пустым.

// Продолжайте извлекать из stack элементы меньшего размера, чем текущий

// элемент и установить их следующий больший элемент в текущий элемент

while (!s.isEmpty() && input[s.peek()] < input[i]) {

result[s.pop()] = input[i];

}

// поместить текущий “индекс” в stack

s.push(i);

}

return result;

}

public static void main(String[] args)

{

int[] input = { 2, 7, 3, 5, 4, 6, 8 };

int[] result = findNextGreaterElements(input);

System.out.println(Arrays.toString(result));

}

Скачать Выполнить код

результат:

[7, 8, 5, 6, 6, 8, -1]

Python

from collections import deque

# Найти следующий больший элемент для каждого элемента в списке

def findNextGreaterElements(input):

# Базовый вариант

if not input:

return

result = [–1] * len(input)

# создает пустой stack

s = deque()

# делаем на каждый элемент

for i in range(len(input)):

# Цикл #, пока у нас не будет большего элемента сверху или stack не станет пустым.

# Продолжайте извлекать элементы из stack меньшего размера, чем текущий

# и установить их следующий больший элемент на текущий элемент

while s and input[s[–1]] < input[i]:

result[s[–1]] = input[i]

s.pop()

# помещает текущий “индекс” в stack

s.append(i)

return result

if __name__ == ‘__main__’:

input = [2, 7, 3, 5, 4, 6, 8]

print(findNextGreaterElements(input))

Скачать Выполнить код

результат:

[7, 8, 5, 6, 6, 8, -1]

Вот еще одно решение на основе stack, в котором элементы обрабатываются справа налево в массиве.

Для каждого элемента x в массиве цикл, пока у нас не будет большего элемента на вершине stack или stack, становится пустым.
Как только stack содержит больший элемент наверху, установите его как следующий больший элемент x и подтолкнуть x на вершине stack. Если стек становится пустым, установите следующий больший x в качестве -1.
Повторите процесс для каждого элемента массива.

Ниже приведена программа на C++, Java и Python, демонстрирующая этот алгоритм:

C++

#include <iostream>

#include <stack>

#include <vector>

using namespace std;

vector<int> findNextGreaterElements(vector<int> const &input)

{

int n = input.size();

vector<int> result(n, –1);

// создаем пустой stack

stack<int> s;

// обрабатываем каждый элемент справа налево

for (int i = n – 1; i >= 0; i—)

{

// цикл до тех пор, пока у нас не будет большего элемента сверху или stack не станет пустым.

while (!s.empty())

{

// извлекаем элементы, которые не больше, чем текущий элемент

if (s.top() <= input[i]) {

s.pop();

}

// следующий больший элемент теперь находится на вершине stack

else {

result[i] = s.top();

break;

}

// поместить текущий элемент в stack

s.push(input[i]);

}

return result;

}

int main()

{

vector<int> input = { 2, 7, 3, 5, 4, 6, 8 };

vector<int> result = findNextGreaterElements(input);

for (int i: result) {

cout << i << ‘ ‘;

}

return 0;

}

Скачать Выполнить код

результат:

7 8 5 6 6 8 -1

Java

import java.util.Arrays;

import java.util.Stack;

class Main

{

public static int[] findNextGreaterElements(int[] input)

{

// базовый вариант

if (input == null) {

return input;

}

int n = input.length;

int[] result = new int[n];

Arrays.fill(result, –1);

// создаем пустой stack

Stack<Integer> s = new Stack<>();

// обрабатываем каждый элемент справа налево

for (int i = n – 1; i >= 0; i—)

{

// цикл до тех пор, пока у нас не будет большего элемента сверху или stack не станет пустым.

while (!s.empty())

{

// извлекаем элементы, которые не больше, чем текущий элемент

if (s.peek() <= input[i]) {

s.pop();

}

// следующий больший элемент теперь находится на вершине stack

else {

result[i] = s.peek();

break;

}

// поместить текущий элемент в stack

s.push(input[i]);

}

return result;

}

public static void main(String[] args)

{

int[] input = { 2, 7, 3, 5, 4, 6, 8 };

int[] result = findNextGreaterElements(input);

System.out.println(Arrays.toString(result));

}

Скачать Выполнить код

результат:

[7, 8, 5, 6, 6, 8, -1]

Python

from collections import deque

def findNextGreaterElements(input):

# Базовый вариант

if not input:

return

n = len(input)

result = [–1] * n

# создает пустой stack

s = deque()

# обрабатывает каждый элемент справа налево

for i in reversed(range(n)):

# Цикл #, пока у нас не будет большего элемента сверху или stack не станет пустым.

while s:

# всплывающие элементы, которые не больше, чем текущий элемент

if s[–1] <= input[i]:

s.pop()

# следующий больший элемент теперь находится на вершине stack

else:

result[i] = s[–1]

break

# помещает текущий элемент в stack

s.append(input[i])

return result

if __name__ == ‘__main__’:

input = [2, 7, 3, 5, 4, 6, 8]

result = findNextGreaterElements(input)

print(result)

Скачать Выполнить код

результат:

[7, 8, 5, 6, 6, 8, -1]

Временная сложность обоих решений на основе stack составляет O(n) поскольку каждый элемент помещается в stack и извлекается из него не более одного раза. Используемое вспомогательное пространство O(n) для stack.

Упражнение: Расширьте решение для кругового массива для кругового поиска, чтобы найти следующий больший элемент.

Источник

Какой алгоритм для поиска максимума в случайном массиве использовать? В статье собрано 5 эффективных must-have алгоритмов.

Если хочешь подтянуть свои знания, загляни на наш курс «Алгоритмы и структуры данных», на котором ты:

углубишься в решение практических задач;
узнаешь все про сложные алгоритмы, сортировки, сжатие данных и многое другое.

Ты также будешь на связи с преподавателем и другими студентами.

В итоге будешь браться за сложные проекты и повысишь чек за свою работу 🙂

Интересно, хочу попробовать

Самый быстрый и простейший алгоритм

Следует пояснить, что под “быстротой” алгоритма будет подразумеваться его асимптотическая сложность, а не физическое время выполнения.

В действительности, единственный способ точно найти самое большое число в случайном массиве будет перебор каждого числа в поисках максимума. Поэтому сложность такого алгоритма – O(N). Они называются линейными.

Простейшая реализация алгоритма на С:

#include <stdio.h>
 
int main()
{
  int array[100];
  int maximum, size, index = 0;
 
  printf("Введите длину массива (не больше 100)n");
  scanf("%d", &size);
 
  printf("Введите %d целых чисел массиваn", size);
  for (int i = 0; i < size; i++)
    scanf("%d", &array[i]);
 
  maximum = array[0]; // За изначальный максимум берем первый элемент массива
 
  for (int i = 1; i < size; i++)
  {
    if (array[i] > maximum)
    {
       maximum  = array[i];
       index = i;
    }
  }
 
  printf("Максимум находится в позиции %d и его значение %d.n", index, maximum);
  return 0;
}

А как насчет распараллеливания?

После прочтения абзаца выше многие могут предложить поиск максимума с помощью параллельных вычислений, потому что он будет быстрее. И это так, если мы говорим о физическом времени. Но несмотря на то, сколько у вас есть процессов, вам всё равно придется просмотреть каждый элемент массива. Сложность алгоритма остается такой же, O(N).

Рассмотрим ситуацию на примере. Есть 200 карточек, на каждой из которых случайное число. Ваша задача найти карточку с самым большим числом. Допустим, друг согласился помочь, забрав половину карточек. Теперь каждый из вас ищет максимум из 100 карточек, вместо 200. Как только вы оба закончите, останется сравнить максимумы обеих половин. Время сократилось вдвое, но просмотреть пришлось все 200 карточек.

Сама по себе задача является так называемой чрезвычайно параллельной задачей, что ещё раз подтверждает возможность её решения именно распараллеливанием, без ущерба для конечного результата.

Задача о разборчивой невесте

Есть ещё один вариант нахождения максимума в случайном массиве.
Идем по первой половине всех значений в массиве. Запоминаем самое большое. Назовём его Х. Далее проходим по второй половине. Когда (и если) находим значение, которое больше Х, останавливаемся. Обозначим его Y. Какова вероятность того, что Y – максимум в массиве?

Чтобы это утверждение было истинным, Y должно находиться во второй половине массива. А так как значения в массиве случайны, шанс такого = 50%. Тогда если второй максимум присутствует в первой половине, это гарантирует, что найден правильный максимум.

Вероятность, что второй максимум в первой половине также = 50%. Посему вероятность, что и второй максимум в первой половине, и первый максимум во второй половине, равна 25%.

В итоге, такой алгоритм гарантирует точность 25% в нахождении максимума в массиве случайных чисел. Можно улучшить алгоритм, если искать второй максимум не в первой половине (1/2), а в 1/e (основание натурального логарифма) части массива. Этот способ впервые был предложен для решения задачи о разборчивой невесте или задачи секретаря (The Secretary Problem).

Аналоговый алгоритм

Спагетти-сортировка – прекрасный аналоговый алгоритм для решения задачи нахождения максимума в массиве.

Представим, что в массиве только N целых чисел. Возьмите N не приготовленных палочек спагетти, длина каждой сопоставляется с единственным значением в массиве.
Соберите спагетти в руку. Аккуратно, чтобы не сломать, поставьте горсть на ровную поверхность. В результате выше всех будет видна самая длинная (максимум) соломинка.

Асимптотическая сложность такого алгоритма – O(1). Но в цифровом мире он не применим.

Квантовый алгоритм

Алгоритм Гровера (или схема Гровера) используется в квантовых вычислениях для решения задач перебора. С его помощью сложность поиска максимума уменьшается до O(sqrt(N)) (большая О от корня N).

Данный способ решения может быть применен только на квантовом компьютере, что сильно умаляет его полезность в современном мире, но его нельзя не упомянуть.

Источник

Хотите дополнить? Ждём ваши предложения в комментариях 😉

Источник

1. Подход грубой силы

C

Java

Python

2. Использование stack

C++

Java

Python

C++

Java

Python

Самый быстрый и простейший алгоритм

А как насчет распараллеливания?

Задача о разборчивой невесте

Аналоговый алгоритм

Квантовый алгоритм

Хотите дополнить? Ждём ваши предложения в комментариях 😉

Вам также может понравиться

Как составить протокол если гражданин не имеет регистрации

Как найти инвестора для бизнеса в беларуси

Как найти книгу в минске

Добавить комментарий Отменить ответ