买卖股票的最佳时机 II
假设有一个数组，它的第i个元素是一个给定的股票在第i天的价格。设计一个算法来找到最大的利润。你可以完成尽可能多的交易(多次买卖股票)。然而,你不能同时参与多个交易(你必须在再次购买前出售股票)。
给出一个数组样例[2,1,2,0,1], 返回 2
解题
参考买卖股票的最佳时机I ，求出相邻两天的股票差值，当差值大于0的时候，完成一次交易。当连续一段的交易，可以理解为：该连续交易的起始是购买，连续交易的结束时卖出。这样求出的就是一个子段的最大值。对所有的子段求和就是答案了。
对这个子数组：
相邻元素差的数组：
假设这个起始交易的利润最大：
,这个值也就等于上面数组的和
如何判断这个子数组的起始位置？
我们要求的是相邻子数组的的差应该大于等于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;
}
};