在一個範圍內查找數組單元格中的數字總和

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應該始終位於最小值和最大值之間，也就是說，對於每個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.由於max是8，所以不允許得分10.在步驟3之後，得分可以是0,2,4或8.因此，在該遊戲中，最大得分可以獲取在序列的末尾是8

輸入格式

輸入的第一行包含四個整數N，b，min和max，其含義是，如上所述。第二行輸入包含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％