Posts tagged as “stock”

花花酱 LeetCode 123. Best Time to Buy and Sell Stock III

By zxi on November 28, 2021

You are given an array prices where prices[i] is the price of a given stock on the i^th day.

Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Example 4:

Input: prices = [1]
Output: 0

Constraints:

1 <= prices.length <= 10⁵
0 <= prices[i] <= 10⁵

Solution: DP

A special case of 花花酱 LeetCode 188. Best Time to Buy and Sell Stock IV where k = 2.

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int maxProfit(vector<int>& prices) {

constexpr int k = 2;

const int n = prices.size();

vector<int> balance(k + 1, INT_MIN);

vector<int> profit(k + 1, 0);

for (int i = 0; i < n; ++i)

for (int j = 1; j <= k; ++j) {

balance[j] = max(balance[j], profit[j - 1] - prices[i]);

profit[j] = max(profit[j], balance[j] + prices[i]);

}

return profit[k];

}

};

花花酱 LeetCode 188. Best Time to Buy and Sell Stock IV

By zxi on November 28, 2021

You are given an integer array prices where prices[i] is the price of a given stock on the i^th day, and an integer k.

Find the maximum profit you can achieve. You may complete at most k transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

Constraints:

0 <= k <= 100
0 <= prices.length <= 1000
0 <= prices[i] <= 1000

Solution: DP

profit[i][j] := max profit by making up to j sells in first i days. (Do not hold any share)
balance[i][j] := max balance by making at to up j buys in first i days. (Most hold a share)

balance[i][j] = max(balance[i-1][j], profit[i-1][j-1] – prices[i]) // do nothing or buy at i-th day.
profit[i][j] = max(profit[i-1][j], balance[i-1][j] + prices[i]) // do nothing or sell at i-th day.

ans = profit[n-1][k]

Time complexity: O(n*k)
Space complexity: O(k)

C++

// Author: Huahua

class Solution {

public:

int maxProfit(int k, vector<int>& prices) {

const int n = prices.size();

vector<int> balance(k + 1, INT_MIN);

vector<int> profit(k + 1, 0);

for (int i = 0; i < n; ++i)

for (int j = 1; j <= k; ++j) {

balance[j] = max(balance[j], profit[j - 1] - prices[i]);

profit[j] = max(profit[j], balance[j] + prices[i]);

}

return profit[k];

}

};

美国程序员收入几何？要交多少税？

By zxi on February 15, 2020

无论是在中国还是美国，程序员/软件工程师都是视为高收入人群。并不是因为收入真的很高，而是比起大多数（隐形）高收入行业来说公开透明，被讨论的比较多而已。

今天花花就和大家一起聊一下美国程序员的收入情况。主要内容分三块：收入的组成，大厂之间收入的横向比较，税务问题。

Part 1. 收入的组成

年薪（Package）

基本工资（Base salary）：基本工资主要由级别决定，不同级别之间的差距不大。每级可能差10%左右。
奖金（Bonus）：和基本工资挂钩，是基本工资的10%～25%，主要由公司业绩和个人绩效决定。
股票（RSU）：一般来说股票每年都会refresh，每次奖励都要要分4年来发，有些公司每年25%，有些公司第一年只有5%。如果你提前离职，后面的股票就都没了。奖励时的金额和级别/个人表现有关，最后（卖出时）的收入则和公司股价直接成正比。比如奖励$10,000的RSU，近期公司股价$50，则为200股。4年后公司股价涨到$100，就变成了$20,000（这里有没有考虑税的问题）。对于高级别员工来说，股票是大头，可能比基本工资还要高。

一次性补贴

签字费（Sign-on Bonus）：$20,000 ~ $100,000+ 不等，不同厂家之间区别很大。通常需要保证工作一年以上，不然需要退回。
搬家费（Relocation Bonus）：$3,000 ~ $10,000 不等。可用于搬场，汽车运输，租车等。
临时居住（Corporate housing）：有些公司对外地/外国员工提供14-30天不等的临时居住，通常为酒店式公寓。名义价值$250+/天。也就是$3,500 ~ $7,500的价值。利用这个时间段去找公寓就不会显得手忙脚乱，同时也可以剩下一笔小钱。湾区一居室的公寓基本上都要$3,000/月，和别人合租的话可以降低到$1,500~$2,000/月。当然住私人、远一些或者条件比较差的（比如车库）可以再降低到$1,000/月。

福利

401K 公司匹配（Employer match）401K是美国的退休计划（养老金），主要由个人出资（每年有上限），可以用来投资基金，实现财富增长，并提供一部分税收优惠。公司会匹配员工的投资，通常为30%～50%（50%是上限）。目前401K每年上限为$19,500，公司最多匹配$9,750。如果你不存放401K，这笔钱就没有了。
免费午餐：天下哪有免费午餐？湾区软件公司就有。不仅午餐免费，早餐，晚餐，饮料，水果，零食等统统免费。有些甚至连周末也有。每顿饭的名义价值大概在$15~$20左右。如果三餐都在公司吃：$17.5*20*3 = $1,050/月。如果你自己不喜欢做饭，也不想出去下馆子，在公司吃饭可以省下不少钱。
医疗保险：之前视频中没有提到，美国医疗特别贵，所以保险也很贵，一年也要好几千块美元。
交通补贴：免费的班车，公共交通补贴，打车补贴等。

Part 2. 大厂横向比较

选取了Facebook, Microsoft, Apple, Google 和 Amazon等传统大厂来比较，也有收入比它们高的。这里只比较了base + bonus + stock。所有数据全部来自于 levels.fyi 网站。

首先每家公司对级别的要求/定义不太相同，我们先看一张天梯图：

Entry level: Apple ICT2/ICT3, Amazon: L4, Google L3, Facebook E3, Microsoft 59,60
Intermediate level: Apple ICT3, Amazon: L5, Google L4, Facebook E4, Microsoft 61,62
Senior level: Apple ICT4, Amazon L6, Google L5, Facebook E5, Microsoft 63,64

从这张图就可以明显的看到，绿色部分的base salary增加的不多，主要是蓝色的stock部分随着级别呈指数增长。同时我也给出了近5年该公司的股票走势。长期持有增长型公司的股票收入相当可观。

微软相对前面两家来说package就要低一些，主要是stock比较少。

亚麻和苹果作为两家完全不同类型的公司没想到在薪资方面倒是出奇的统一。

Part 3. 税务问题

最后我们来简单聊一下税务问题。首先是免费声明：花花无法为你提供任何税务方面的服务和建议，下面的所有内容仅供参考，不能作为你报税依据。

我们假设一年的总收入为$200,000，单身，位于加州。
首先是扣除部分：

401K pre-tax, $20,000
Standard deduction $12,000

那么taxable income就是$168,000

我们来看一下2019年联邦税表

收入超过$160,726的，需要交$32,748.50 + 32% * ($16,800 – $160,726) = $35,076. 综合税率：$35,076 / $168,000 = 20.88%

除了联邦税之外还有州税：

落在9.3%这一档，大概要交$14k，综合税率 8.33%。

你以为这样就完了吗？还要交社会保险6.2%，上限$8k+。医疗保险1.45%，上限$2k。

总的税收 = $35k + $14k + $8k + $2k ~= $60k

综合税率：$60k / $168k = 35.7%

税前$200k, 税后$108 + 20k = $128k，扣除401k和股票，到手的现金大概也就$90k/year，每个月$7,500，房租/水电网 $3000+，汽车+保险 $400+，还要吃饭，买衣服什么的，就没剩多少钱了。。。在哪里都不容易啊。所以有些人选择住房车/车库，骑车或坐班车，在公司吃饭，穿公司发的t-shirt。哦对了，如果你买了房，就算还清了贷款，每个月还要交$1500～$3000+的房产税，而且一交就是一辈子。

花花酱 LeetCode 309. Best Time to Buy and Sell Stock with Cooldown

By zxi on January 6, 2018

题目大意：给你每天的股价，没有交易次数限制，但是卖出后要休息一天才能再买进。问你最大收益是多少？

Say you have an array for which the i^th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

prices = [1, 2, 3, 0, 2]

maxProfit = 3

transactions = [buy, sell, cooldown, buy, sell]

Idea:

Solution:

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

int maxProfit(vector<int>& prices) {

int sold = 0;

int rest = 0;

int hold = INT_MIN;

for (const int price : prices) {

int prev_sold = sold;

sold = hold + price;

hold = max(hold, rest - price);

rest = max(rest, prev_sold);

}

return max(rest, sold);

}

};

Related Problems:

花花酱 LeetCode 121. Best Time to Buy and Sell Stock

花花酱 LeetCode 121. Best Time to Buy and Sell Stock

By zxi on December 22, 2017

题目大意: 给你一只股票每天的价格，如果只能做一次交易（一次买进一次卖出）问你最多能赚多少钱。

Problem:

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

Idea:

Solution 1:

C++

// Author: Huahua

// Runtime: 6 ms

class Solution {

public:

int maxProfit(vector<int>& prices) {

const int n = prices.size();

if (n < 1) return 0;

vector<int> min_prices(n);

vector<int> max_profit(n);

min_prices[0] = prices[0];

max_profit[0] = 0;

for (int i = 1; i < n; ++i) {

min_prices[i] = min(min_prices[i - 1],

prices[i]);

max_profit[i] = max(max_profit[i - 1],

prices[i] - min_prices[i - 1]);

}

return max_profit[n - 1];

}

};

C++ / reduce to maximum subarray

// Author: Huahua

// Runtime: 6 ms

class Solution {

public:

int maxProfit(vector<int>& prices) {

int n = prices.size();

if (n < 2) return 0;

vector<int> gains(n - 1, 0);

for (int i = 1; i < n; ++i)

gains[i - 1] = prices[i] - prices[i - 1];

return max(0, maxSubArray(gains));

}

private:

// From LC 53. Maximum Subarray

int maxSubArray(vector<int>& nums) {

vector<int> f(nums.size());

f[0] = nums[0];

for (int i = 1; i < nums.size(); ++i)

f[i] = max(f[i - 1] + nums[i], nums[i]);

return *std::max_element(f.begin(), f.end());

}

};

Related Problems:

花花酱 LeetCode 309. Best Time to Buy and Sell Stock with Cooldown