股票交易类算法_股票交易算法

问题1：简单买卖：只允许买卖一次Best Time to Buy and Sell Stock

本题意思就是你得到一系列在接下来几天的股票价格，现在你被允许只用一次交易（就是买进再卖出）来获取最大利益。 

 求一组数中最大差问题（只能是后面的数减前面的数）

转化一下思路，求出两两相邻数的差，求一系列差值的最大连续子序列和，问题就转化为 

Maximum Subarray问题

注意两点：

收益不能为负，所以如果求出来的值小于0，输出0

如果给出的数组只有一个数，也输出0

public int maxProfit(int[] prices) {
        int length = prices.length;
        if(length < 2)return 0;
    	int sum = 0,max = Integer.MIN_VALUE;
    	for(int i =1;i<length;i++){
    	    int diff = prices[i]-prices[i-1];
    	    sum += diff;
    	    if(max < sum)max=sum;
    	    if(sum < 0)sum = 0;
    	}
    	if(max < 0)return 0;
    	return max;
    }

问题2：简单买卖：可以买卖无穷多次

意思是买卖股票时可以不计买卖次数，但是必须在买之前先把以前的股票卖掉。然后求能获利最大的额度。 这样的话也很简单，只要遇见下一天的价格比这一天价格高的话，就卖出。

求所有上升期差价的总和。

public int maxProfit(int[] prices) {
        int length = prices.length;
        int ret = 0;
        for(int i = 0;i<length-1;i++){
            if(prices[i]<prices[i+1]){
               ret +=  (prices[i+1]-prices[i]);
            }
        }
        return ret;
    }

问题3：挑选股票

挑选规则：给定一个股票集合vector<int> stocks,股票编号为1,2,3...,N。挑选规则：

1. 从左往右，第一个开始，每隔一个就删除一个；比如第一次删除的是1,3,5...

2. 从右往左，最后一个开始，每隔一个就删除一个。

重复1,2步骤，直至列表中只剩一只股票。

输入：股票个数N。

输出：最后剩下的那只股票编号。

示例：输入20，输出6。

#include <iostream>
#include <vector>
using namespace std;
 
int pickStock(vector<bool>& stocks, bool left, int* leftStart, int* rightStart);
 
int main()
{
	int input;
	cin >> input;
	vector<bool> stocks(input, true);
	if (input <= 1) {
		cout << "1" << endl;
		return 0;
	}
 
	int leftStart = 0;
	int rightStart = input - 1;
	for (int i = 0; i < input/2; ++i) {
		int leftSize = pickStock(stocks, true, &leftStart, &rightStart);
		if (leftSize == 1) {
			cout << leftStart+1 << endl;
			break;
		}
		leftSize = pickStock(stocks, false, &leftStart, &rightStart);
		if (leftSize == 1) {
			cout << leftStart+1 << endl;
			break;
		}
	}
	
	return 0;
}
 
/**
 * 挑选函数
 * 第二个参数标识从左往右，还是从右往左
 * 第三个参数是从左往右第一个没有被删除的位置
 * 第四个参数是从右往左第一个没有被删除的位置
 * 
 * 返回值：剩余股票数目
 * */
int pickStock(vector<bool>& stocks, bool left, int* leftStart, int* rightStart) {
	if (*leftStart == *rightStart) {
		return 1;
	}
	int size = stocks.size();
	int existSize = 0;
	if (left) {//从左往右
		for (int i = *leftStart; i < size; ++i) {
			if (stocks[i]) {
				existSize++;
				if (existSize%2 == 1) {
					stocks[i] = false;
				}
			}
		}
	} else {//从右往左
		for (int i = *rightStart; i >= 0; --i) {
			if (stocks[i]) {
				existSize++;
				if (existSize%2 == 1) {
					stocks[i] = false;
				}
			}
		}
	}
	int leftSize = 0;
	bool hasLeftStart = false;
	for (int i = 0; i < size; ++i) {
		if (stocks[i]) {
			leftSize++;
			*rightStart = i;
			if (!hasLeftStart) {
				*leftStart = i;
				hasLeftStart = true;
			}
		}
	}
	return leftSize;
}