Complexity in Java

Question

I have a general question about my complexity in my Code. Since I am doing some things from Codeforces, complexity matters the first time to me. Problemset: https://codeforces.com/problemset/problem/1554/A

Code:

import java.util.Arrays; 
import java.util.List; 
import java.util.Scanner; 
import java.util.Collections;

public class main {
    public static void main(String[] args) {
        doCalculation();
    }

    public static void doCalculation () {
        Scanner sc = new Scanner(System.in);

        long n = sc.nextLong();

        for (int i = 0; i < n; i++) {
            int numbersInRow = sc.nextInt();
            long [] numbersToRead = new long[numbersInRow];
            for(int j = 0; j < numbersInRow; j++) {
                numbersToRead[j] = sc.nextLong();
            }

            long maxMultiplication = 0;

            for(int k = 0; k < numbersInRow; k++) {
                for (int m = k + 1; m < numbersInRow; m++) {
                    //Von jetzt an von 1 bis 2; von 1 bis 3; von 2 bis 3
                    long[] subarray = subArray(numbersToRead, k, m);
                    //System.out.println(Arrays.toString(subarray));

                    long min = Arrays.stream(subarray).min().getAsLong();
                    //System.out.println(min);

                    long max = Arrays.stream(subarray).max().getAsLong();
                    //System.out.println(max);

                    long multiplicationEveryArray = min * max;

                    if(multiplicationEveryArray > maxMultiplication) {
                        maxMultiplication = multiplicationEveryArray;
                    }
                }
            }
            System.out.println(maxMultiplication);
        }
    }
    
    public static long[] subArray(long[] array, int beg, int end) {
        return Arrays.copyOfRange(array, beg, end + 1);
    } 
}

I think copyRange has complexity O(n) and subarry has the same complexity. What are some ways to improve my complexity without taking a different approach?

Answer 1

Usually, these problems are set up in a way that the brute-force method will finish in a million years.

Looking at the examples, my first intuition kind of was that you only need to look at neighboring numbers, making this an O(n) problem.

If you have f(1,2) and f(2,3) then f(1,3) will definitely be the max of f(1,2) and f(2,3). The product of the first and last elements is impossible to be the max as it means that at least one of them has to be smaller than or equal to the second element in the middle to be considered, making the product smaller than or equal to the product of "just neighbors".

You can continue on through induction to reach to the conclusion that f(1,n+1) will be max(f(1,2), f(2,3), ... f(n,n+1)).

In order to get rid of the O(n^2) loop try

for(int k = 0; k < numbersInRow - 1; k++) {
  final int product = numbersToRead[k] * numbersToRead[k+1];
  if (product > maxMultiplication) {
    maxMultiplication = product;
  }
}