发表于 | 分类于

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

解法1：DP with O(N) 空间

从左往右维护一个最小的price,那么转换方程就可以写成dp[i] = Math.max(dp[i - 1], price[i] - min),
其中dp[i]表示的是前i个数中如果只能交易一次的最大利润，不一定要以i结尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int maxProfit(int[] prices) {
	
	if (prices == null || prices.length == 0) {
		return 0;
	}
	
	int[] profit = new int[prices.length];
	int min = prices[0];
	int res = 0;
	for (int i = 1; i < prices.length; i++) {
		profit[i] = Math.max(profit[i - 1], prices[i] - min);
		min = Math.min(min, prices[i]);
		res = Math.max(res, profit[i]);
	}
	
	return res;
}

解法2：DP with O(1) 空间

从左往右维护当前的最小值，并且计算每一个累积和和最小值的差，取最大的作为结果.
这题用DP的思路是dp[i] = max(dp[i - 1], A[i] - min)， 所以就是也要维护一个min，实际上并不需要维护dp数组，只要不停更新min就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int maxProfit(int[] prices) {
	
	if (prices == null || prices.length == 0) {
		return 0;
	}
	
	int minPrice = prices[0]; 
	int res = 0;
	
	for (int i = 0; i < prices.length; i++) {
		res = Math.max(prices[i] - minPrice, res);
		minPrice = Math.min(minPrice, prices[i]);
	}
	
	return res;
}

发表于 | 分类于

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.
Practice

解法1：DP with O(N) 空间

用经典的DP思想可以解决，dp数组存的是以i结尾的前i个数字的max subarray，那么可以得到这样的递推关系
dp[i] = Max(dp[i - 1] + A[i], A[i])
意思就是说以i结尾的最大的子数组和要么是自己，要么是前一个子数组和加上自己。可以写出如下的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
public int maxSubArray(int[] nums) {
	
	int[] dp = new int[nums.length];
	dp[0] = nums[0];
	int max = dp[0];
	
	for (int i = 1; i < nums.length; i++) {
		dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
		max = Math.max(dp[i], max);
	}
	
	return max;
}

解法1优化: DP with O(1) 空间

观察上面的解法可以发现，实际上我们不需要维护一个数组来记录每一个点的最大和。
我们可以只维护一个变量sum,来记录从0到i的和。如果sum一旦小于0，那么对下一个dp数值的计算一定用不上sum,所以此时可以设置为0. 代码如下

1
2
3
4
5
6
7
8
9
10
11
12
public int maxSubArray(int[] nums) {
	
	int sum = 0;
	int max = Integer.MIN_VALUE;
	for (int i = 0; i < nums.length; i++) {
		sum += nums[i];
		max = Math.max(sum, max);
		if (sum < 0) {
			sum = 0;
		}
	return max;
}

解法2: 前缀和数组的思路，O(N) time + O(1) space

基本思想是：如果把数组中每一个元素都加起来，我们可以得到一个累积的和，那么这个问题实际上就变成了
best time to buy and sell stock I的问题，从左至右寻找最小的mininum sum,然后将当前的sum和minSum相减再和全局的最大值比较得出结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int maxSubArray(int[] nums) {
	
	int sum = 0;
	
	int min = 0;
	
	int profit = nums[0];
	
	for (int i = 0; i < nums.length; i++) {
		profit = Math.max(sum + nums[i] - min, profit);
		sum += nums[i];
		min = Math.min(sum, min);
	}
	return profit;
}

解法3：用Divide & Conquer思想：O(NlogN)

具体的思路是把原来的array一分为二，那么最大的子数组和一定是在1.左面的数组，2.右面的数组，3.跨越左面和右面的数组
左面和右面用递归的方式计算。跨越中点的数组一定包含mid point,往右面扫描找出最大的，往左面扫描找出最大的，最后比较三个数得出结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public int maxSubArray(int[] nums) {
	return helper(nums, 0, nums.length - 1);
}
public int helper(int[] A, int left, int right) {
	if (left >= right) {
		return A[left];
	}
	
	// Divide into left and right array
	int mid = left + (right - left) / 2;
	int lmax = helper(A, left, mid - 1);
	int rmax = helper(A, mid + 1, right);
	
	// Merge and Conquer
	int mmax = A[mid];
	int temp = mmax;
	// Scan to left
	for (int i = mid - 1; i >= left; i--) {
		temp += A[i];
		mmax = Math.max(mmax, temp);
	}
	
	// Scan to right
	temp = mmax;
	for (int i = mid + 1; i <= right; i++) {
		temp += A[i];
		mmax = Math.max(mmax, temp);
	}
	return Math.max(mmax, Math.max(lmax, rmax));
}

发表于 | 分类于

在看一个技术博客的时候无意间发现了博主使用的这个开源项目Hexo，它是一个基于Node.js的快速搭建blog的框架。
觉得很好就拿来搭了现在的这个大提摩，搭建这个Hexo需要的步骤非常简单。

安装Hexo

安装Hexo之前需要确保已经安装了Node.js和Git。安装Hexo时就可以按照官网执行：

1
$ npm install -g hexo-cli

Deployer

如果部署到github需要一个deployer

1
npm install hexo-deployer-git --save

大道至简的Theme

我用的这个主题是一个博主fork过来专门用于Hexo的，个人觉得简单干净大气。安装也很简单

1
2
3
$ git clone https://github.com/tufu9441/maupassant-hexo.git themes/maupassant
$ npm install hexo-renderer-jade --save
$ npm install hexo-renderer-sass --save

要注意的是这个安装方法中jade已经改名成pug了，不过对我们使用这个theme好像问题也不大。

其他反面，等慢慢体验多了有什么想记一笔的再写上来。

写博客和发布

1
$ hexo new post "post-name"

编辑分类(category)

直接打开post文件，按照如下的格式修改即可

1
2
3
4
5
6
7
8
9
10
---
title: 显示的post的名字
date: 2016-04-11 14:12:26
category:
- 技术总结
- 在这里列举分类
tags:
- Hexo
- 用这个方法加入tags
---

发布

1
hexo generate --deploy

发表于

总是感觉自己想学的和已经学得东西都很多，却零零散散，开了这个blog，想整理一些自己的资料。在这里我会总结或者分享一些技术相关的文章，工作学习生活体会，还有投资理财，量化交易的心得等等。不务正业的时候也会分享一些自家的深夜料理，以小餐日料和中国家常菜为主，偶尔会有黑暗料理乱入。