vye_csdn-CSDN博客

原创动态规划_买卖股票的最佳时机|||_1

1.【问题描述】买卖股票的最佳时机 III 2.【思路】参考：Best Time to Buy and Sell Stock III 题目要求是“最多可以完成两笔交易”。则一共有三种情况：不交易；完成一次交易；完成两次交易。其中，不交易的最大收益是0，完成一次交易包含当天买入当天卖出的情况，所以“完成一次交易”的方案已经包含了“不交易”，故总共有两种交易方案：完成一次交易和完成

2016-10-08 16:49:13 1567

原创买卖股票的最佳时机||_1

1.【问题描述】买卖股票的最佳时机 II 2.【思路】参考：Best Time to Buy and Sell Stock II 题目要求“你可以完成尽可能多的交易(多次买卖股票)。然而,你不能同时参与多个交易，你必须在再次购买前出售股票”。举个例子说明。股票价格数组是 [1,2,3]，则收益最大的交易方案是：第一笔交易：第1天买入，第2天卖出；第二笔交易：第2天买入，第3

2016-10-08 14:28:52 421

原创买卖股票的最佳时机|_1

1. 【问题描述】买卖股票的最佳时机 2.【思路】参考：Best Time to Buy and Sell Stock I 首先要搞清楚“最多进行一次股票交易”是什么意思。举个例子，假设股票价格数组是prices，则“最多进行一次股票交易”意味着： 2.1 不进行股票交易，这样收益是0； 2.2 进行一次股票交易，例如在第 i 天买入股票，在第 j 天卖出股票

2016-10-08 10:58:04 548

原创动态规划_最大子数组||_1

1. 【问题描述】最大子数组|| 2. 【思路】假设给定数组共有N个元素，令符号（i, j）表示子数组nums[i,i+1,...,j]的最大子数组的和，则所求为： max{（0，0）+（1，N-1），（0，1）+（2，N-1）,...,（0，N-2）+（N-1，N-1）}，即需要求出（0，i）和（i+1，N-1），其中 0dp0保存（0，i）的值，初始化dp0[0]=（0,

2016-10-06 10:46:02 479

原创动态规划_最大子数组|||_1

1. 【问题描述】最大子数组||| 2. 【思路】参考：LintCode:Maximum Subarray III 假设给定数组共有N个元素，需要找到K个不重合的子数组使其和最大。令符号（i, j）表示在数组前i个元素中找到j个不重合的和最大的子数组的和，符号[a,b]表示在子数组nums[a,a+1,...,b]中找到一个最大子数组，返回最大子数组的和。则有：（i, j）

2016-10-06 08:33:52 357

原创分而治之_最大子数组_1

1. 【问题描述】最大子数组 2. 【思路】参考算法导论采用分而治之的策略。假设数组nums共有N个元素，下标范围 0—N-1，令过程maxBE(nums,beg,end)可以返回nums的下标范围 beg—end的子数组的最大子数组和，即nums[beg,...,end]的最大子数组和，下面对maxBE过程进行分析： (1). beg==end 则直接返回nums[be

2016-10-05 10:53:46 470