【Leetcode】贪心

题目编号

53 121

53. 最大子序和

解题思路

因为负数加负数更小，所以当目前总和为负数时，跟下一个负数只取一个较大的负数。

代码

public int maxSubArray(int[] nums) {
        int[] dt = new int[nums.length];
        dt[0] = nums[0];
        int maxSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            // 找出正数最多的子序列
            // 负数相加只会越来越小，所以当总和小于零时遇上负数直接把前面舍弃
            dt[i] = Math.max(dt[i - 1],0) + nums[i];
            if (dt[i] > maxSum) {
                //因为会遍历到底，所以要记录遍历途中最大的数
                maxSum = dt[i];
            }
        }
        return maxSum;
    }

121. 买卖股票的最佳时机

解题思路

因为只买卖一次，所以只要找到最大值前面的最小值就行了，每次模拟买入卖出情况，找出最大差值，解决问题。

代码

class Solution {
    public int maxProfit(int[] prices) {
		// 输入为空时，返回0
        if (prices.length == 0) return 0;
        int buy = prices[0];
        int profit = 0;
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < buy) {
                // 模拟买入，如果买入价格比之前低，就买入备选
                buy = prices[i];
            } else if (prices[i] > buy) {
                // 每次模拟卖出的情况
                profit = prices[i] - buy;
                if (profit > maxProfit) {
                    // 如果利润大于最大利润，就卖出备选
                    maxProfit = profit;
                }
            }
        }
        return maxProfit;
    }
}