1500802034呂占英

#include "stdafx.h"
#include "iostream"
using namespace std;
class Solution {
/**
* @param prices: Given an integer array
* @return: Maximum profit
*/
public:
int maxProfit(int[] prices)
{
// write your code here
int null;
if ( null == prices || 0 == prices.length)
return 0;
int sumProfit = 0;
for (int i = 1; i<prices.length; i++)
{
int tmpsum = maxProfit(prices, 0, i) + maxProfit(prices, i + 1, prices.length - 1);
sumProfit = Math.max(sumProfit, tmpsum);
}
return sumProfit;
}
public:
int maxProfit(int[] prices , int s, int e)
{
if (e <= s) return 0;
int min = prices[s];
int maxProfit = 0;
for (int i = s + 1; i <= e; i++)
{
maxProfit = Math.max(maxProfit, prices[i] - min);
min = Math.min(min, prices[i]);
}
return maxProfit;
}
};