Задачка: наибольшая возрастающая непрерывная подпоследовательность (longest increasing contiguous subsequence)

Требуется в заданной последовательности найти наибольшую возрастающую непрерывную подпоследовательность. Например, дана последовательность {1,2,3,-1,2,3,4,5}. В этой последовательности наибольшая возрастающая непрерывная подпоследовательность начинается с позиции 4 и имеет длину 4, т.е. это подпоследовательность {-1,2,3,4,5}.

Запишем всю последовательность в массив. Будем последовательно проходить массив. Если элемент массива больше предыдущего, то увеличим счетчик длины последовательности на 1. Если элемент массива меньше или равен предыдущему, то поставим счетчик длины в 1 (т.к. последовательность), и метку начала подпоследовательности поставим равной текущему индексу. При этом проверим, если длина только что окончившейся подпоследовательности больше предыдущей максимальной, то максимальную длину меняем.

Входные данные передаются так: на первой строчке файла стоит кол-во чисел в последовательности. На всех остальных строчках в начале стоит следующее число в последовательности. Пример входного файла:

8
1
2
3
-1
2
3
4
5

Код:

import java.io.*;
public class Problem1 {
 
    static int[] a;
    static int startIndex;
    static int maxLength;
 
    static void findMaxIncrSubseq() {
        if (a.length==1) {
            startIndex = 0;
            maxLength = 1;
            return;
        }
        int start = startIndex = 0;
        int length = maxLength = 1;
        for (int i=1; i<a.length; i++) {
            if (a[i] > a[i-1]) {
                length++;
            } else {
                if (length > maxLength) {
                    maxLength = length;
                    startIndex = start;
                }
                length = 1;
                start = i;
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        FileInputStream fstream = new FileInputStream("in.txt");
        DataInputStream in = new DataInputStream(fstream);
        BufferedReader br = new BufferedReader(new InputStreamReader(in));
        String strLine;
        strLine = br.readLine();
        int size = Integer.parseInt(strLine);
        a = new int[size];        
        int i=0;
        while ((strLine = br.readLine()) != null)   {
            a[i] = Integer.parseInt(strLine);
            i++;
        }
        in.close();
        findMaxIncrSubseq();
        System.out.println("Longest increasing contiguos subsequence starts from " + startIndex + " and is of length " + maxLength);
        System.out.println("Longest increasing contiguos subsequence:");
        for (i=startIndex; i<startIndex+maxLength; i++) {
            System.out.println(a[i]);
        }
    }
}

Пример файла in.txt:

12
1
2
3
-10
5
6
7
8
9
0
1
2

Пример вывода:

>java Problem1
Longest increasing contiguos subsequence starts from 3 and is of length 6
Longest increasing contiguos subsequence:
-10
5
6
7
8
9

Задачка на динамическое программирование: листинг операций

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

Заведем массив ops, который будет содержать в себе признаки операций для каждого числа. 1 - операция вычитания единицы, 2 - операция деления на два, 3 - операция деления на три.

Код:

public class Problem {
 
    static int[] ops;
 
    static int getMinSteps(int n) {
        if (n==1) return 0;
        else {
            int[] steps = new int[n+1];
            ops   = new int[n+1];
            steps[0] = -1;
            steps[1] = 0;
            ops[0] = ops[1] = -1;
            for (int i=2; i<=n; i++) {
                steps[i] = steps[i-1]+1;
                ops[i] = 1;
                if (i%2==0) {
                    int oldvalue = steps[i];
                    steps[i] = min(steps[i],steps[i/2]+1);
                    if (steps[i] != oldvalue) ops[i] = 2;
                } 
                if (i%3==0) {
                    int oldvalue = steps[i];
                    steps[i] = min(steps[i],steps[i/3]+1);
                    if (steps[i] != oldvalue) ops[i] = 3;
                }
            }
            return steps[n];
        }
    }
 
    static int min(int a, int b) {
        return a < b ? a : b;
    }    
 
    public static void main(String[] args) {
        if (args.length != 1) {
            System.err.println("Should be exectly one argument (natural number)!");
            return;
        }
        int n;
        try {
            n = Integer.parseInt(args[0]);
        } catch (NumberFormatException nfe) {
            System.err.println("Argument should be a natural number!");
            return;
        }
        if (n <= 0) {
            System.err.println("Wrong argument!");
            return;
        }
        System.out.println("Minimum number of steps: " + getMinSteps(n));
        printOps(n);        
    }
 
    static void printOps(int n) {
        System.out.println("Operations:");
        int i=n;
        while (i>1) {
            if (ops[i] == 1) {
                System.out.println("-1 ("+i+"-1="+(i-1)+")");
                i--;
            } else if (ops[i] == 2) {
                System.out.println("/2 ("+i+"/2="+(i/2)+")");
                i=i/2;
            } else if (ops[i] == 3) {
                System.out.println("/3 ("+i+"/3="+(i/3)+")");
                i=i/3;
            }
        }
    }
}

Пример вывода программы:

>java Problem 11212
Minimum number of steps: 15
Operations:
-1 (11212-1=11211)
/3 (11211/3=3737)
-1 (3737-1=3736)
-1 (3736-1=3735)
/3 (3735/3=1245)
/3 (1245/3=415)
-1 (415-1=414)
/3 (414/3=138)
/3 (138/3=46)
-1 (46-1=45)
/3 (45/3=15)
/3 (15/3=5)
-1 (5-1=4)
-1 (4-1=3)
/3 (3/3=1)

Задачка на динамическое программирование: Minimum steps to one

Формулировка задачи на английском:

On a positive integer, you can perform any one of the following 3 steps. 
1.) Subtract 1 from it. ( n = n - 1 )  , 
2.) If its divisible by 2, divide by 2. ( if n % 2 == 0 , then n = n / 2  )  , 
3.) If its divisible by 3, divide by 3. ( if n % 3 == 0 , then n = n / 3  ). 

Now the question is, given a positive integer n, find the minimum number of steps that takes n to 1
eg: 
1.)For n = 1 , output: 0       
2.) For n = 4 , output: 2  ( 4  /2 = 2  /2 = 1 )    
3.)  For n = 7 , output: 3  (  7  -1 = 6   /3 = 2   /2 = 1 )

Теперь формулировка на русском языке (в моем переводе):

Дано натуральное число n (не равное нулю). Над ним можно совершить одну из трех операций:
1) вычесть единицу из него (n-1)
2) разделить на два (n/2)
3) разделить на три (n/3)

Для данного числа n найти минимальное число операций, в результате которых получается единица. 
Пример: 
1) n=1, ответ: 0
2) n=4, ответ: 2 (/2, /2)
3) n=7, ответ: 3 (-1, /3, /2)

Рассмотрим решение.

Для каждого данного n непонятно, какая из операций приведет к минимальному числу шагов. Поэтому нужно попробовать все варианты и выбрать из них вариант с минимальным числом шагов.
Если n == 1, то F(n) = 0.
Иначе (если n>1):
F(n) = 1 + min(F(n-1),F(n/2),F(n/3)).
При этом каждый раз нужно проверять, делится ли n без остатка на два или на три.

Решение в коде на Java:

public class Problem {
 
    static int getMinSteps(int n) {
        if (n==1) return 0;
        else if (n==2 || n==3) return 1;
        else if (n==4) return 2;
        else {
            int[] steps = new int[n+1];
            steps[0] = -1;
            steps[1] = 0;
            steps[2] = steps[3] = 1;
            steps[4] = 2;
            for (int i=5; i<=n; i++) {
                steps[i] = steps[i-1]+1;
                if (i%2==0) {
                    steps[i] = min(steps[i],steps[i/2]+1);
                } 
                if (i%3==0) {
                    steps[i] = min(steps[i],steps[i/3]+1);
                }
            }
            return steps[n];
        }
    }
 
    static int min(int a, int b) {
        return a < b ? a : b;
    }    
 
    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        System.out.println(getMinSteps(n));
    }
}

Задачка простенькая, но как вводный пример в динамическое программирование сгодится.
В коде нет, конечно, проверки на допустимые значения n (не проверяется, чтобы n было больше нуля), также нет проверки на отсутствие аргумента в командной строке. Главное здесь - познакомиться с подходом, который предлагает динамическое программирование для решения такого рода задач.