« Back
in Leetcode Java Array Dynamic Programming read.

Leetcode 121 Best Time to Buy and Sell Stock.

Problem 121 Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

This problem is really similar to Problem 53 Maximum Subarray.

So the most direct way to solve is change the list to price difference list. Then use dynamic programming to solve the max sum.

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length==0||prices.length==1){
            return 0;
        }

        int[] nums=new int[prices.length-1];
        for(int i=0;i < prices.length-1;i++){
            nums[i]=prices[i+1]-prices[i];
        }


        int length=nums.length;
        int newsum=nums[0];
        int max=nums[0];

        for(int i=1;i < length;i++){
            newsum=Math.max(nums[i],newsum+nums[i]);
            max=Math.max(max,newsum);
        }
        if(max < 0){
            max=0;
        }
        return max;
    }
}
comments powered by Disqus