剑指 Offer 63. 股票的最大利润 & AcWing

题目假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖该股票一次可能获得的最大利润是多少?示例示例1输入: [7,1,5,3,6,4]输出: 5解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。示例2输入: [7,6,4,3,1]输出: 0解释: 在这

- 阅读全文 -

剑指 Offer 47. 礼物的最大价值 & AcWing

题目在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?示例示例1输入:[ [1,3,1], [1,5,1], [4,2,1] ] 输出: 12解释: 路径 1→3→5→2→1 可以拿到最多价值的

- 阅读全文 -

AcWing_55_连续子数组的最大和

题目输入一个 非空 整型数组,数组里的数可能为正,也可能为负。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n)。数据范围:数组长度 [0,1000]。示例示例1输入:[1, -2, 3, 10, -4, 7, 2, -5]输出:18代码解法:dpclass Solution { public: int maxSubArray(vector<

- 阅读全文 -

剑指 Offer 42. 连续子数组的最大和

题目输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。示例示例1输入: nums = [-2,1,-3,4,-1,2,1,-5,4]输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。代码dp做法O(n)class Solution { public int maxSubArray(int[] nums) {

- 阅读全文 -

剑指 Offer 10- II. 青蛙跳台阶问题

题目一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。示例示例1输入:n = 2输出:2示例2输入:n = 7输出:21示例3输入:n = 0输出:1代码迭代public int numWays(int n) { int a = 1, b =

- 阅读全文 -