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

它可以在线性时间和线性内存中完成。这个想法是：找到数组的每个后缀的最小值和每个前缀的最大值，然后找到两者之间的差异最大的点。如果您需要索引，您还必须存储达到每个前缀的最大值/最小值的索引，而不仅仅是差值。

于 2012-10-05T16:47:01.777 回答
0

对 a[] 进行预排序会使过程变得复杂并影响性能。这不是必需的，因此我们将 a[] 保留为未排序。

然后（已编辑，因为我在您的代码正文中阅读了 j>=i，而不是问题描述/标题中的 i>=j，我现在认为这是必需的（我没有仔细阅读您的编码细节); 无论如何，这两个品种很容易相互派生。）

// 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 回答