Êý×éÎÊÌâ

    public int FindGreatestSumOfSubArray(int[] array) {
         int res = Integer.MIN_VALUE; 
         int sum = 0;
         for(int i = 0; i < array.length; i++){
             sum += array[i];
             res = Math.max(res, sum);
             sum = sum < 0 ? 0 : sum;
         }
        return res;
    }

     public void swap(int []arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public int partition(int[] arr, int left, int right){
        int less = left - 1;
        int more = right;
        int cur = left;
        while(cur < more){
            if(arr[cur] < arr[right]){
                swap(arr, ++less, cur++);
            }else if(arr[cur] == arr[right]){
                cur++;
            }else{
                swap(arr, --more, cur);
            }
        }
        swap(arr, right, more);
        return more;
    }


    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(input == null || k < 1 || k > input.length) return res;
        int index = partition(input, 0, input.length - 1);
        while(index != k - 1){
            if(index > k - 1){
                index = partition(input, 0, index - 1);

            }else{
                index = partition(input, index + 1, input.length - 1);
            }
        }

        for(int i = 0; i < k; i++){
            res.add(input[i]);
        }
        return res;
    }

public static boolean VerifySquenceOfBST(int [] sequence) {
    if (sequence == null || sequence.length < 1) return false;
    return helper3(sequence, 0, sequence.length - 1);
}
public static boolean helper3(int [] arr, int left, int right){
    int i = left;
    int root = arr[right];
    for(i = left; i < right; i++){
        if (arr[i] > root){
            break;
        }
    }
    int j = i;
    for(; j < right; j++){
        if (arr[j] < root){
            return false;
        }
    }
    return  (i >= 1 ? helper3(arr, left,i - 1) : true )&& (i < right ? helper3(arr, i, j) : true);
}

   class PrintMinNumberCom implements Comparator<String> {
       @Override
       public int compare(String o1, String o2) {
           return (o1 + o2).compareTo(o2 + o1);
       }
   }

    public String PrintMinNumber(int [] numbers) {
        if (numbers == null || numbers.length ==0) return "";
        String[] strings = new String[numbers.length];
        for (int i = 0 ;i < numbers.length; i++)
            strings[i] = String.valueOf(numbers[i]);
        Arrays.sort(strings,new PrintMinNumberCom());
        String res ="";
        for (int i = 0; i < strings.length; i++){
            res += strings[i];
        }
        return res;

    }

 public int nthUglyNumber(int n) {
        int [] res =new int[n];
        res[0] = 1;
        int index2 = 0, index3 = 0, index5 = 0;
        int factor2 = 2, factor3 = 3, factor5 = 5;
        for (int i = 1 ;i < n;i++){
            int min = Math.min(Math.min(factor2,factor3),factor5);
            res[i] = min;
            if (min == factor2 ){
                index2++;
                factor2 = 2*res[index2];
            }

            if (min == factor3 ){
                index3++;
                factor3 = 3*res[index3];
            }

            if (min == factor5 ){
                index5++;
                factor5 = 5*res[index5];
            }
        }

        return res[n-1];
    }