Leetcode 53. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

click to show more practice.

More practice:If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle

Analysis:

Keep two values, one is the sum for all values. One is the global max sum. If the sum is less than 0, make it to be 0.

Time complexity: O(n)

Space complexity: O(1)

Code is below:

public class Solution {
    public int maxSubArray(int[] nums) {
        // O(n)
        
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int max = Integer.MIN_VALUE;
        int sum = 0;
        
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            max = Math.max(max, sum);
            sum = Math.max(sum, 0);
        }
        
        return max;
    }
}

Leetcode 121. Best Time to Buy and Sell Stock

Say you have an array for which the i^th 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.

Example 1:

Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

Analysis:
Go through the whole array and maintains the min value and the max profit.

Time complexity: O(n)
Space complexity: O(1)

Code is below:

public class Solution {
    public int maxProfit(int[] prices) {
        // O(n) 
        
        if (prices == null || prices.length == 0) {
            return 0;
        }
        
        // The smallest value and the profit
        int min = Integer.MAX_VALUE;
        int profit = 0;
        
        for (int price : prices) {
            // update the min value and the max profit
            min = price < min ? price : min;             profit = (price - min) > profit ? price - min : profit;
        }
        
        return profit;
    }
}