目录
- 350-两个数组的交集
- 283-移动零
- 1-两数之和
- 25-K 个一组翻转链表
- 581-最短无序连续子数组
- 合并区间
- 螺旋矩阵
- 数组中相加和为0的三元组
- 数组中出现次数超过一半的数字
- 字符串出现次数的TopK问题
- 206-反转链表
- 160-相交链表
- 19-删除链表的倒数第N个节点
- 21-合并两个有序链表
- 31-下一个排列
- 链表K位翻转
- 链表排序-归并算法
- 判断链表中是否有环
- 设计LRU缓存结构
- 两个链表的第一个公共结点
- 两个链表生成相加链表
- 合并N个有序链表
- 链表内指定区间反转
买卖股票的最好时机(一)
访问量:1410
一、简介
假设你有一个数组prices,长度为n,其中prices[i]是股票在第i天的价格,请根据这个价格数组,返回买卖股票能获得的最大收益
1.你可以买入一次股票和卖出一次股票,并非每天都可以买入或卖出一次,总共只能买入和卖出一次,且买入必须在卖出的前面的某一天
2.如果不能获取到任何利润,请返回0
3.假设买入卖出均无手续费
二、实现
/** * d[i][0] // 代表第i天没持有 * d[i][1] // 代表第i天持有 * @param prices int整型一维数组 * @return int整型 */ func maxProfit( prices []int ) int { // write code here maxVal := 0 dp := make(map[int]map[int]int) dp[0] = make(map[int]int) dp[0][0] = 0 dp[0][1] = 0 - prices[0] for i:=1; i < len(prices); i++ { dp[i] = make(map[int]int) // 计算当前没持有的最大值 // 前一天也没持有 或前一天持有今天卖出 dp[i][0] = getMaxVal(dp[i-1][0], dp[i-1][1] + prices[i]) if dp[i][0] > maxVal { maxVal = dp[i][0] } // 计算当前持有的最大值 // 前一天也持有 或前一天没持有今天买入 dp[i][1] = getMaxVal(dp[i-1][1], - prices[i]) if dp[i][1] > maxVal { maxVal = dp[i][1] } } return maxVal } func getMaxVal(n1, n2 int) int { if n1 >= n2 { return n1 } return n2 }
本文为原创文章,请尊重辛勤劳动,如需转载,请保留本文地址
若您感觉本站文章不错,读后有收获,不妨赞助一下?
我要赞助