0

私はこれをもっと速くしようとしています。ツリーを使用することを検討しましたが、それが実際に役立つかどうかはわかりません。

問題は、ほとんどの場合、可能な最大値をすべて計算する必要がないことだと思いますが、どこに線を引くべきかわかりません

ご意見ありがとうございます、ジャスパー

public class SpecialMax {

    //initialized to the lowest possible value of j; 
    public static int jdex = 0; 
    //initialized to the highest possible value of i; 
    public static int idex; 
    //will hold possible maximums 
    public static Stack<Integer> possibleMaxs = new Stack<Integer> (); 

    public static int calculate (int[] a){
        if (isPositive(a)){ 
            int size = a.length; 
            int counterJ; 
            counterJ = size-1;

            //find and return an ordered version of a

            int [] ordered = orderBySize (a);

            while (counterJ>0){
                /* The first time this function is called, the Jvalue will be 
                 * the largest it can be, similarly, the Ivalue that is found
                 * is the smallest
                 */
                int jVal  = ordered[counterJ];  
                int iVal  = test (a, jVal);
                possibleMaxs.push(jVal-iVal);
                counterJ--; 
            }

            int answer = possibleMaxs.pop(); 

            while (!possibleMaxs.empty()){
                if (answer<possibleMaxs.peek()){
                    answer = possibleMaxs.pop(); 
                } else { 
                    possibleMaxs.pop(); 
                }
            }

            System.out.println("The maximum of a[j]-a[i] with j>=i is: ");
            return answer;
        } else {
            System.out.println ("Invalid input, array must be positive"); 
            return 0; //error
        }
    }

    //Check to make sure the array contains positive numbers
    public static boolean isPositive(int[] a){ 
        boolean positive = true; 
        int size = a.length; 

        for (int i=0; i<size; i++){
            if (a[i]<0){
                positive = false; 
                break; 
            }
        }


        return positive; 
    }

    public static int[] orderBySize (int[] a){
         //orders the array into ascending order
         int [] answer = a.clone(); 
         Arrays.sort(answer);
         return answer; 
    }

         /*Test returns an Ival to match the input Jval it accounts for 
          * the fact that jdex<idex. 
          */
    public static int test (int[] a, int jVal){
        int size = a.length;
        //initialized to highest possible value
        int tempMin = jVal; 
        //keeps a running tally 
        Stack<Integer> mIndices = new Stack<Integer> (); 

        //finds the index of the jVal being tested
        for (int i=0; i<size; i++) { 
            if (jVal==a[i]){
                //finds the highest index for instance
                if (jdex<i){
                    jdex = i;
                }
            }
        }

        //look for the optimal minimal below jdex;  
        for (int i=0; i<jdex; i++){
            if (a[i]<tempMin){
                tempMin = a[i]; 
                mIndices.push(i);
            }
        }

        //returns the index of the last min
        if (!mIndices.empty()){
           idex = mIndices.pop(); 
        }

        return tempMin; 
    }

}
4

2 に答える 2

1

線形時間と線形メモリで実行できます。アイデアは次のとおりです。配列の各サフィックスの最小値と各プレフィックスの最大値を見つけてから、2 つの差が最大になるポイントを見つけます。差分値だけでなく、インデックスが必要な場合は、各プレフィックスの最大/最小に達したインデックスも保存する必要があります。

于 2012-10-05T16:47:01.777 に答える
0

a[] を事前に並べ替えると、手順が複雑になり、パフォーマンスが低下します。必要ないので、a[] はソートしないままにします。

次に（編集済み、問題の説明/タイトルの i>=j ではなく、コードの本文で j>=i を読んだため、これが必要であると想定しています（コーディングの詳細は調べませんでした） ); いずれにせよ、この 2 つの変種は互いに簡単に派生させることができます。)

// initialize result(indices)
int iFound = 0;
int jFound = 0;
// initialize a candidate that MAY replace jFound
int jAlternative = -1; // -1 signals: no candidate currently available

// process the (remaining) elements of the array - skip #0: we've already handled that one at the initialization
for (int i=1; i<size; i++)
{
  // if we have an alternative, see if that combines with the current element to a higher "max".
  if ((jAlternative != -1)  && (a[jAlternative]-a[i] > a[jFound]-a[iFound]))
  {
    jFound = jAlternative;
    iFound = i;
    jAlternative = -1;
  }
  else if (a[i] < a[iFound]) // then we can set a[iFound] lower, thereby increasing "max"
  {
    iFound = i;
  }
  else if (a[i] > a[jFound])
  { // we cannot directly replace jFound, because of the condition iFound>=jFound,
    // but when we later may find a lower a[i], then it can jump in:
    // set it as a waiting candidate (replacing an existing one if the new one is more promising).
    if ((jAlternative = -1) || (a[i] > a[jAlternative]))
    {
      jAlternative = i;
    }
  }
}

double result = a[jFound] - a[iFound];
于 2012-10-05T21:42:31.167 に答える