题目描述:

假设你有一个数组，其中第i个元素是第i天给定股票的价格。
设计一个算法找到最大利润，你也许最多只能完成两次交易。

• 请注意，不得同时进行多笔交易(即您必须在再次购买前卖出股票)

Example1

Input: [3,3,5,0,0,3,1,4]
Output: 6

Explanation
第四天买入，第六天卖出，利润是3-0=3.
然后第七天买入，第八天卖出，利润是4-1=3

Example2

Input: [1,2,3,4,5]
Output: 4

Explanation
第一天买入，第五天卖出，利润是5-1=4.
注意你不能第一天买进，第二天买进然后一起卖掉。因为你在同一时间同时进行多个交易时，必须在再次买进之前卖出

Example 3:

Input: [7,6,4,3,1]
Output: 0

Explanation
在这个例子中，没有交易做成因为最大利润是零

C++输入格式

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        
    }
};

范例

子函数

class Solution {
public:
    int maxProfit(vector<int> &prices) 
    {
        if (prices.size() <= 1) return 0;
        else 
        {
            int K = 2; // number of max transation allowed
            int maxProf = 0;
            vector<vector<int> > f(K+1, vector<int>(prices.size(), 0));
            //创建一个二维数组，行数为k+1，列数为 prices.size()，初始化全为零 
            for (int kk = 1; kk <= K; kk++) 
            {
                int tmpMax = f[kk-1][0] - prices[0];
                cout<<tmpMax<<" "; 
                for (int ii = 1; ii < prices.size(); ii++) 
                {
                    f[kk][ii] = max(f[kk][ii-1], prices[ii] + tmpMax);
                    cout<<f[kk][ii]<<" "; 
                    tmpMax = max(tmpMax, f[kk-1][ii] - prices[ii]);
                    cout<<tmpMax<<" ";
                    maxProf = max(f[kk][ii], maxProf);
                    cout<<maxProf<<" "<<endl;
                }
            }
            return maxProf;
        }   
    }
};

主函数

int main()
{
    vector<int> vec;
    int i=0;
    int m =0;
    //int a[10]={7,6,4,3,1};
    //int a[10]={1,2,3,4,5};
    int a[10]={7,1,5,3,6,4};
    //int a[10]={7};
    //int a[10]={9,9};
    for(i=0;i<6;i++)
    {
       vec.push_back(a[i]);
    }

    vector<int>::iterator pos;
    //声明一个迭代器，来访问vector容器。作用:遍历或指向vector容器的元素 
    cout<<"输入数组:";
    for(pos = vec.begin();pos!=vec.end();pos++)
    {
        cout<<*pos<<" ";
    } 
    cout<<endl;
    Solution sol;
    m = sol.maxProfit(vec);
    cout<<m<<endl; 
    return 0;
}

测试用例