Поиск суммы чисел в ячейках массива в диапазоне

Question

Я готовлюсь к конкурсу кодирования. В архивах я нашел этот вопрос:

Вам предоставляется последовательность из N натуральных чисел i1, i2, ..., iN. Кроме того, вам присваивается начальное целое число b и нижнее и верхнее целочисленные пределы min и max соответственно. Заметим, что 0 ≤ min ≤ b ≤ max всегда.

Последовательная игра воспроизводится следующим образом. Первоначально ваш счет b. На шаге 1 вы можете добавить i1 в b или вычесть i1 из b, чтобы получить новый счетb1. На шаге 2 вы обновляете b1, добавляя или вычитая i2, чтобы получить новый балл b2. Действуя таким образом, на шаге j вы обновляете bj-1, добавляя или вычитая ij, чтобы получить новый балл bj. Правило состоит в том, что каждый балл bj всегда должен находиться между min и max, включая: то есть для каждого j, 1 ≤ j ≤ N, это должно быть так, что min ≤ bj ≤ max. Ваша окончательная оценка - bN, после использования последнего числа в последовательности.

Ваша цель - максимизировать свой окончательный результат, играя в соответствии с правилами. Если невозможно завершить все N шагов, не выходя за пределы min и max, ваш счет равен -1.

Например, предположим, что последовательность цифр у вас [2,3,4], b равна 5, min равно 0, а max - 8. После шага 1 оценка может быть 3 или 7. После шага 2 , оценка может быть 0, 4 или 6. Оценка 10 не допускается, так как max равно 8. После шага 3 оценка может быть 0, 2, 4 или 8. Таким образом, в этой игре максимальная оценка вы можете получить в конце последовательности равна 8.

формат входного

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

Выходной формат

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

TestData

Во всех случаях, N ≤ 103 и 0 ≤ ≤ мин ≤ B ≤ макс 103.

Пример ввода

3 5 0 8 2 3 4 

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

8 

---

Теперь, я три d решить эту проблему, используя рекурсивную технику, но ее слишком медленно. Я проверил все возможные меры. Может быть, я и ошибаюсь. Вот мой код:

import java.io.*; 

class seq2 

{ 

    public static void recursive(int ar[],int turn,int sum,int max,int min,int n,int mega[]) 

    { 

        if(turn!=n) 

        { 

            if(ar[turn]+sum<=max) 

            { 

                sum=sum+ar[turn]; 

                recursive(ar,turn+1,sum,max,min,n,mega); 

                sum=sum-ar[turn]; 

            } 

            if(sum-ar[turn]>=0) 

            { 

                sum=sum-ar[turn]; 

                recursive(ar,turn+1,sum,max,min,n,mega); 

                sum=ar[turn]+sum; 

            } 

            if((ar[turn]+sum>max)&&(sum-ar[turn]<min)) 

            { 

                sum=-1; 

            } 

        } 

        else 

        { 

            if(sum>mega[0]) 

            { 

                mega[0]=sum; 

            } 

        } 

    } 

    public static void main(String args[])throws IOException 

    { 

        DataInputStream in=new DataInputStream(System.in); 

        int n=Integer.parseInt(in.readLine()); 

        int b=Integer.parseInt(in.readLine()); 

        int min=Integer.parseInt(in.readLine()); 

        int max=Integer.parseInt(in.readLine()); 

        System.out.println(); 

        int ar[]=new int[n],a; 

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

        { 

             a=Integer.parseInt(in.readLine()); 

             ar[i]=a; 

        } 

        int mega[]={-1}; 

        recursive(ar,0,b,max,min,n,mega); 

        System.out.println(mega[0]); 

    } 

} 

---

Может кто-нибудь предложить лучший метод для решения этого?

Answer 1

public static void recursive(int ar[], int turn, int sum, int max, int min, int mega[]) 
{ 
    int plus, minus; 
    if (turn != ar.length) 
    { 
     plus = sum + ar[turn]; 
     if (plus <= max) 
      recursive(ar, turn + 1, plus, max, min, mega); 

     minus = sum - ar[turn]; 
     if (minus >= min) 
      recursive(ar, turn + 1, minus, max, min, mega); 
    } 
    else if (sum > mega[0]) 
     mega[0] = sum; 
} 

удалось сократить время на 30%