几道算法题练习下

/**

 * 解题思路：

 * 比如给定一组数组，[1，2，3，6，9，3，10]

 * 最多可以2次去获取最大的利益，可以用2分的思想，分成2部分，

 * 从0元素开始遍历分别求出左右2边的最大利益，求出的左右2边最大的利益即为解

 */

classSolution {

    publicstaticintmaxProfit(int[] prices) {

        // write your code here

        if(null==prices||0==prices.length) return0;

         intsumProfit = 0;

         for(inti=1;i<prices.length;i++){

              inttmpsum = maxProfit(prices, 0, i)

                + maxProfit(prices, i+1, prices.length-1);

              sumProfit = Math.max(sumProfit, tmpsum);

         }

         returnsumProfit;

    }

    publicstaticintmaxProfit(int[] prices,ints,inte){

         if(e<=s) return0;

         intmin = prices[s];

         intmaxProfit = 0;

         for(inti=s+1;i<=e;i++){

              maxProfit = Math.max(maxProfit, prices[i]-min);

              min = Math.min(min, prices[i]);

         }

         returnmaxProfit;

    }

    publicstaticvoidmain(String[] args) {

     intarr [] =  {4,4,6,1,1,4,2,5};

     System.out.println(maxProfit(arr));

}

}

publicclassTest8 {

publicstaticvoidmain(String[] args) {

//输入n个整数和一个整数

Scanner input = newScanner(System.in);

System.out.println("请输入n个整数，数量任意,以逗号分隔");

String str = input.next();

System.out.println("请输入一个整数：");

intx = input.nextInt();

//将n个整数的字符串转换为数组

String arr1[] = str.split(",");

int[] arr2 = newint[arr1.length];

for(inti=0;i<arr1.length;i++){

arr2[i] = Integer.parseInt(arr1[i]);

}

System.out.println(Arrays.toString(arr2));

//判断并输出n个整数中有几对的和等于x

intcount = 0;

for(inti=0;i<arr2.length-1;i++){

for(intj = i+1;j<arr2.length;j++){

if(arr2[i]+arr2[j]==x){

count++;

}

}

}

System.out.println(count);

}

}

publicclassQuick {

publicstaticvoidmain(String[] args) {

intarr [] = {90,60,70,50,40,80,20,100,10};

sort(arr,0,arr.length-1);

System.out.println(Arrays.toString(arr));

}

publicstaticvoidsort(intarr[], intlow, inthigh) {

//设置两个变量l、h，排序开始的时候：l=0，h=N-1

intl = low;

inth = high;

//以第一个数组元素作为关键数据，赋值给key，即key=A[0]

intkey = arr[low];

//重复操作，直到i=j

while(l < h) {

//从h开始向前搜索，即由后开始向前搜索(h--)，找到第一个小于key的值arr[h]，将arr[h]和arr[l]互换

while(l < h && arr[h] >= key)

h--;

if(l < h) {

inttemp = arr[h];

arr[h] = arr[l];

arr[l] = temp;

l++;

}

//从l开始向后搜索，即由前开始向后搜索(l++)，找到第一个大于key的arr[l]，将arr[l]和arr[h]互换；

while(l < h && arr[l] <= key)

l++;

if(l < h) {

inttemp = arr[h];

arr[h] = arr[l];

arr[l] = temp;

h--;

}

}

//对前一部分进行快速排序

if(l > low)

sort(arr, low, l - 1);

//对前一部分进行快速排序

if(h < high)

sort(arr, l + 1, high);

}

}