最大股票价格

问题描述：假设有一个数组，数组中的元素代表一只股票在不同天的价格走向，你可以用你手里的现金多次买进卖出股票，请给出获益最大的方案。允许多次买和卖

    public int getMaxProfits(int[] arr) {
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            int min = i;
            for (int j = i + 1; j <= arr.length - 1; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                } else if (arr[j] > arr[min]) {
                    if (j < arr.length - 1 && arr[j] > arr[++j]) {//低价买入，高价出手
                        sum += arr[--j] - arr[min];
                        i = j;
                        break;

                    }
                                //j=arr.length - 1,直接卖掉
                    sum += arr[j] - arr[min];

                }
                break;

            }
        }
        return sum;
    }



public static void main(String args[]) {
        MyCalc calc = new MyCalc();
        int arr[] = { 20, 2, 8, 5, 11, 9, 8, 30 };
        int arr1[] = { 2, 5, 3, 8, 7, 12, 1, 20, 16 };
        int sum = calc.getMaxProfits(arr);
        System.out.println(sum);
        int sum1 = calc.getMaxProfits(arr1);
        System.out.println(sum1);
    }

解法2：思想：如果T+2天价格比T日高，则卖出

public int getMaxProfit(int[] arr) {

        int sum = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] < arr[i + 1]) {
                sum += arr[i + 1] - arr[i];
            }
        }
        return sum;

    }

如果只允许一次买卖

public int getMaxProfits(int[] arr) {
        int sum = 0;

        int max = -1;
        for (int j = 0; j < arr.length - 1; j++) {
            if (arr[j] < arr[j + 1]) {
                max = j + 1;
            }
        }
        if (max > 0) {
            sum = arr[max] - arr[0];

            for (int i = 1; i < arr.length; i++) {

                if (sum < (arr[max] - arr[i])) {
                    sum = arr[max] - arr[i];
                }
            }
            return sum;
        }
        return 0;
    }

题目同上
// Say you have an array for which the ith element is the price of a given stock on day i.

// If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

// Example 1:
// Input: [7, 1, 5, 3, 6, 4]
// Output: 5

// max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
// Example 2:
// Input: [7, 6, 4, 3, 1]
// Output: 0

    
    public int maxProfit(int[] a){
        if(a.length<=0){
            return 0;
        }
        int max=0;
        int min=a[0];
        
        for(int i=1;i<a.length;i++){
            if(a[i]<min){
                min=a[i];
            }
            else{
                max=Math.max(max, a[i]-min);
            }
        }
        return max;
    }

如果允许多次买卖

public int maxProfitWithMultiple(int[] a){
        if(a.length<=0){
            return 0;
        }
        int min=a[0];
        int total=0;
        for(int i=1;i<a.length;){
            if(a[i]<=min){
                min=a[i];
                i++;
            }
            else {
                if(i<a.length-1 && a[i]>a[i+1]){
                    total+=a[i]-min;
                    
                    min=a[i+1];
                    i=i+2;
                }
                else if(a[i]>min){   //i=a.length-1
                    total+=a[i]-min;
                    i++;
                }
            }
        }
        return total;
    }