範囲内の配列のセル内の数値の合計を求める

Question

私はコーディング競争の準備をしています。アーカイブで私はこの質問を見つけました：

あなたはN個の正の整数i1、i2、...、iNのシーケンスが与えられます。さらに、開始整数bと、整数上限値minとmaxをそれぞれ指定します。常に0≤min≤b≤maxであることに注意してください。

シーケンスゲームは以下のように実行されます。最初はスコアはbです。ステップ1では、i1をbに追加するか、bからi1を減算して新しいscoreb1を得ることができます。ステップ2では、i2を加算または減算してb1を更新し、新しいスコアb2を取得します。このようにして、ステップjでは、ijを加算または減算してbj-1を更新し、新しいスコアbjを得る。各スコアbjは常にminとmaxの間にあるべきであるという規則があります。つまり、各jについて1≦j≦Nであり、min≤bj≦maxの場合である必要があります。シーケンスの最後の数字を使用した後、最終スコアはbNです。

あなたの目標は、ルールに従ってプレイしながら、あなたの最終得点を最大にすることです。範囲の最小値と最大値を外れることなくすべてのN個のステップを完了する方法がない場合、スコアは-1です。

たとえば、数字のシーケンスが[2,3,4]、bが5、最小が0、最大が8であるとします。ステップ1の後、スコアは3または7になります。ステップ2スコアは0,4または6にすることができます.maxは8であるため、スコア10は許されません。ステップ3の後、スコアは0,2,4または8になります。したがって、このゲームでは、最大スコアあなたは、配列の終わりに得ることができる8

入力フォーマット

ある入力の最初の行は、その意味は上記で説明した通りである4つの整数N、B、minとmaxを含んでいます。 2行目の入力には、N個のスペースで区切られた整数が含まれています。

出力形式

あなたの出力が1つの整数、あなたが達成できる最大の最終スコアからなる単一の行でなければなりません。全ての場合においてTESTDATA

、N≤103と0≤分≤Bは≤最大≤103

サンプル入力

3 5 0 8 2 3 4 

サンプル出力

8 

---

今、私はトライ再帰的手法を使用することでこの問題を解決していますが、遅すぎます。私は可能なすべての取り決めをチェックした。多分私は間違っていた。ここに私のコードは次のとおりです。

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; 
} 

は