分治法求解数组元素最大差

Question

如果一个人在知道了股票每天的股价以后，对该股票进行投资，问什么时候买入和卖出(注意这里有先后顺序）能取得最大的收益。其数学模型就是，给定一个整数数组，a[1],a[2],.,a[n]，每一个元素a[i]可以和它左边（a[i-1],a[i-2],.,a[0]）元素做差，求这个数组中最大的差值。分治法求解，写出时间复杂度和设计思路

Answer 1

import java.util.Scanner;
public class Test2 {
    public static void max_min(int []a,int left,int right,int []maxnum,int []minnum)
    {
        if (left==right)   //当只有一个元素时候，直接得出最大值和最小值
        {
            maxnum[0]=a[left];
            minnum[0]=a[right];
        }
        else if (left+1==right)//当数组中有两个元素时，直接判断哪个元素大，哪个元素小
        {
            if (a[left]>a[right])
            {
                maxnum[0]=a[left];
                minnum[0]=a[left];
            }
            else
            {
                maxnum[0]=a[right];
                minnum[0]=a[left];
            }
        }
        else     //当数组元素的个数大于2以上的操作。
        {
            int m=(left+right)/2;
            //int lmax=0,lmin=0,rmax=0,rmin=0;
            int lmax[]={0};
            int lmin[]={0};
            int rmax[]={0};
            int rmin[]={0};

            max_min(a,left,m,lmax,lmin);
            max_min(a, m+1, right, rmax, rmin);

               // maxnum=lmax>rmax?lmax:rmax;
               // minnum=lmin<rmin?lmin:rmin;
            if(lmax[0]>rmax[0])
            {
                maxnum[0]=lmax[0];
            }
            else
            {
                maxnum[0]=rmax[0];
            }
            if(lmin[0]<rmin[0])
            {
                minnum[0]=lmin[0];
            }
            else
            {
                minnum[0]=rmin[0];
            }
        }
        //System.out.println("最大值："+maxnum);
        //System.out.println("最小值: "+minnum);

    }
    public static void main(String[] args)
    {
        int array[]={-2,9,1,-4,6};
        int []Max=new int[1];  //java对于实参传递，是采用值传递，所以要改成数组，不能直接使用变量去计算最大值和最小值。
        int []Min=new int[1];
        new Test2().max_min(array,0,array.length-1,Max,Min);

        System.out.println("最大值： "+Max[0]);
        System.out.println("最小值： "+Min[0]);
    }
}