笔试题-股票交易

题目描述

在股市的交易日中，假设最多可进行两次买卖(即买和卖的次数均小于等于2)，规则是必须一笔成交后进行另一笔(即买-卖-买-卖的顺序进行)。给出一天中的股票变化序列，请写一个程序计算一天可以获得的最大收益。请采用实践复杂度低的方法实现。

给定价格序列prices及它的长度n，请返回最大收益。保证长度小于等于500。

测试样例：

[10，22，5，75，65，80]，6

返回：

87

我的解法如下，欢迎参与讨论：
方法一：简单粗暴，时间复杂度O(n)2

        /*
     * 类似冒泡排序，数组中所有元素后减前，找出最大的那个数以及下标位置
     */
    public static void NxN(int[] data){
        int len = data.length;
        
        int max = 0;
        int p1 = -1, p2 = -1;
        int count = 0;
        for(int i=0;i<len ;i++){
            
            for(int j=i;j<len;j++){
                
                if(data[j]-data[i]>max){
                    max = data[j] - data[i];
                    p1 = i;
                    p2 = j;
                }
                count++;
            }
        }
        System.out.println(String.format("最大收益 %s, 下标 (%s,%s), 计算次数 %s", max,p1,p2, count));
    }

方法二: 时间复杂度 O(n)
思路：
1.将数组相邻元素两两相减，构成一个新数组
2.原数组的求解转换成，求新数组的子数组中和最大的一个子数组
3.反推原数组的买入卖出坐标

image.png

public static void O$n$(int[] data){
        int len = data.length;
        /*相邻元素相减，生成新数组*/
        int[] newArr = new int[len-1];
        for(int i=0;i<len-1;i++){
            newArr[i]=data[i+1]-data[i];
        }
        
        
        int m=0, n=0; // m 记录买入的下标， n记录卖出的下标
        int sum = 0; //临时收益
        int maxSum = 0;//最大收益
        
        /*求 最大收益，和卖出时的下标n*/
        for(int i=0;i< newArr.length ;i++){
            
            sum += newArr[i];
            if(sum > maxSum ){
                maxSum = sum;
                n = i;
            }
            /* 如果累加和出现小于0的情况，  
             * 则和最大的子序列肯定不可能包含前面的元素，  
             * 这时将累加和置0，从下个元素重新开始累加  
             */
            if(sum <  0){
                sum = 0;
            }
        }
        
        /*倒推买入下标 m*/
        int tmp = maxSum;
        m = n;
        while((tmp-=newArr[m--])!=0);
        
        /*
         * 由于newArr是由 data 每相邻元素相减生成。
         * 所以 data 与 newArr的下标相差 1 
         */
        n = n+1;
        m = m+1;
        
        System.out.println(String.format("最大收益 %s, 下标 (%s,%s), 计算次数 %s", maxSum, m,n));
    }

主函数：main

public static void main(String[] args) {
        //构造一个数组
        int[] arr = new int[12];
        for(int i=0;i<12; i++){
            int value = (int)(Math.random()*100);
            arr[i] = value;
            System.out.print(value+" ");
        }
        //一次买入卖出 ，最大利润
        System.out.println("方法一：nxn 直接暴力求解");
        NxN(arr);
        System.out.println("方法二：");
        O$n$(arr);
    }