152
int maxProduct(vector<int>& nums) {
if(nums.size()==1)
return nums[0];
vector<vector<int>> dp(nums.size(),vector<int> (2));
if(nums[0]<=0)
dp[0][0]=nums[0];
else
dp[0][1]=nums[0];
for(int i=1;i<nums.size();++i)
{
dp[i][1]=max(dp[i-1][1]*nums[i],dp[i-1][0]*nums[i])>nums[i]?max(dp[i-1][1]*nums[i],dp[i-1][0]*nums[i]):nums[i];
dp[i][0]=min(dp[i-1][0]*nums[i],dp[i-1][1]*nums[i])<nums[i]?min(dp[i-1][0]*nums[i],dp[i-1][1]*nums[i]):nums[i];
}
int max=-100;
for(int k=0;k<nums.size();++k)
{
if(dp[k][1]>max)
max=dp[k][1];
}
return max;
}
714
int maxProfit(vector<int>& prices, int fee) {
int cash=0;
int buy=-prices[0];
for(int i=1;i<prices.size();++i)
{
cash=cash>prices[i]+buy-fee?cash:prices[i]+buy-fee;
buy=buy>cash-prices[i]?buy:cash-prices[i];
}
return cash;
}
网友评论