lintcode:买卖股票的最佳时机 II

时间:2024-01-04 21:05:50

买卖股票的最佳时机 II

假设有一个数组,它的第i个元素是一个给定的股票在第i天的价格。设计一个算法来找到最大的利润。你可以完成尽可能多的交易(多次买卖股票)。然而,你不能同时参与多个交易(你必须在再次购买前出售股票)。

给出一个数组样例[2,1,2,0,1], 返回 2

解题

参考买卖股票的最佳时机I ,求出相邻两天的股票差值,当差值大于0的时候,完成一次交易。当连续一段的交易,可以理解为:该连续交易的起始是购买,连续交易的结束时卖出。这样求出的就是一个子段的最大值。对所有的子段求和就是答案了。

对这个子数组:lintcode:买卖股票的最佳时机 II

相邻元素差的数组:lintcode:买卖股票的最佳时机 II

假设这个起始交易的利润最大:lintcode:买卖股票的最佳时机 II,这个值也就等于上面数组的和

如何判断这个子数组的起始位置?

我们要求的是相邻子数组的的差应该大于等于0,,或者说:这个连续子数组 应该是递增的

通过求其差值是否大于等于0,很好判断是否是递增的。如果直接判断递增,可以通过两层循环,同时第二次循环结束点,又是第一层循环的起始点。

通过相邻元素的差值判断:

class Solution {
/**
* @param prices: Given an integer array
* @return: Maximum profit
*/
public int maxProfit(int[] prices) {
// write your code here
if(prices == null)
return 0;
int sum = 0;
for(int i =0;i< prices.length - 1;i++){
if(prices[i] < prices[i+1])
sum += prices[i+1] - prices[i];
}
return sum;
}
};
 class Solution:
"""
@param prices: Given an integer array
@return: Maximum profit
"""
def maxProfit(self, prices):
# write your code here
sum = 0
if prices == None:
return sum
for i in range(len(prices) - 1):
if prices[i] < prices[i+1]:
sum += prices[i+1] - prices[i]
return sum

Python Code

while循环找出连续递增子数组:

class Solution {
/**
* @param prices: Given an integer array
* @return: Maximum profit
*/
public int maxProfit(int[] A) {
// write your code here
if(A == null || A.length == 0)
return 0;
if(A.length == 1)
return 0;
int sum=0;
int i = 0;
int j = 0;
while(i < A.length && j < A.length){
while(j<A.length-1 && A[j] <= A[j+1])
j++;
// 跳出循环的j 是满足递增序列的最后一个位置 if(j == A.length -1){ // 最后一个元素,结束了
sum += A[j] - A[i];
break;
}else{
sum += A[j] - A[i];
}
i = j + 1;// 下一个位置从新开始
j = j + 1;
}
return sum;
}
};