Оптимизация раздела массива

Нет необходимости снова и снова вычислять умножение подмассива. Это причина, по которой вы получаете ошибку тайм-аута. Вы используете Long для хранения умножения, что приведет к неправильному ответу, вам нужно использовать BigInteger. Ниже подход будет выполнять умножение только один раз. После этого вы можете просто повторить и выяснить различия между ними.

import java.math.BigInteger;
import java.util.Scanner;

public class ParitionArray {
    public static void main(String[] args){
        Scanner s=new Scanner(System.in);
        int size=Integer.parseInt(s.nextLine());
        long arr[]=new long[size];
        for(int i=0;i<size;i++){
            arr[i]=s.nextLong();
        }
        long minIndex=0;
        BigInteger minNo=BigInteger.ZERO;
        BigInteger[] prefixedMult = new BigInteger[size];
        prefixedMult[0] = BigInteger.valueOf(arr[0]);
        for(int k =1; k< size; k++){
            prefixedMult[k] = prefixedMult[k-1].multiply(BigInteger.valueOf(arr[k]));
        }

        for(int k=0;k<size;k++){
            BigInteger part1 = prefixedMult[k]; //multiplication of A[1]*A[2]A[3].........*A[k]
            BigInteger part2 = prefixedMult[size-1].divide(part1);    //multiplication of A[k+1]A[k+2]...........*A[size]

            BigInteger diff = part1.subtract(part2).abs();
            if (k==0){
                minNo=diff;
                minIndex=k;
            }
            //System.out.println(diff);
            if (minNo.compareTo(diff)==1){
                minNo=diff;
                minIndex=k;
            }
        }
        System.out.println("MinNo: "+minNo+" Index: "+minIndex);
    }
}

Вход:

5
2
8
6
5
3

Выход:

MinNo: 74 Index: 1

Я нашел ответ @AndrewScott полезным. Ниже приведена эквивалентная реализация на Java:

 public static void main(String[] args){
        Scanner s=new Scanner(System.in);
        int size=Integer.parseInt(s.nextLine());
        long arr[]=new long[size];
        for(int i=0;i<size;i++){
            arr[i]=s.nextLong();
        }
        long minIndex=0;
        Double minNo=Double.MAX_VALUE;
        Double[] prefixedMult = new Double[size];
        prefixedMult[0] = Math.log10((double)arr[0]);
        for(int k =1; k< size; k++){
            prefixedMult[k] = prefixedMult[k-1] + Math.log10((double)arr[k]);
        }

        for(int k=0;k<size;k++){
            Double part1 = prefixedMult[k]; //multiplication of A[1]*A[2]A[3].........*A[k]
            Double part2 = prefixedMult[size-1] - (part1);    //multiplication of A[k+1]A[k+2]...........*A[size]
            Double diff = Math.abs(part1 - part2);
            if (minNo > diff){
                minNo=diff;
                minIndex=k;
            }
        }
        System.out.println("MinNo: "+minNo+" Index: "+minIndex);
    }

Хотя ответ, предложенный @Mukesh Prajapati, работает, все же есть гораздо более быстрый и лучший способ сделать это.

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

Вы сохраняете совокупную сумму для быстрого поиска. Это позволяет быстро вычислить левую и правую суммы массива. Окончательная минимальная разница находится в ans, а индекс — в переменной index.

void partition(int n, vector<double> &a) {
    double total = 0; vector<double> sum_array_a;

    for(auto &x: a) {
            x = log10(x);
            total += x;
            sum_array_a.push_back(total);
    }

    double ans = INFINITY, index = -1;

    for(int i = 0; i < n; i++) {    // Check for all points if you can split here
            double left = sum_array_a[i];
            double right = total - left;    // Right side sum of elements
            double diff = abs(left - right);
            if (diff < ans) {
                    ans = diff;
                    index = i;
            }
    }

    printf("%f", index);

}