Algorithm

本周的 LeetCode 题目为 121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

想要达到最大利润，那么就要使得买入价格尽可能地低，卖出价格尽可能的高，因此循环遍历数组时，如果遇到当前价格比之前最低买入价还低，则更新最低买入价，进而比较如果当前的利润（当前价-之前的最低价）大于最大的利润，则更新最大的利润。

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        int minPrice = Integer.MAX_VALUE;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            }
            if (maxProfit < prices[i] - minPrice) {
                maxProfit = prices[i] - minPrice;
            }
        }
        return maxProfit;
    }
}

Review

本周 Review 的英文文章为：开源没有被破坏

想必很多人都知道 log4j 最近发生的事，没人捐助原作者，这是谁的错呢？作者任何如果 FOSS（*和开源）被破坏，那么我们今天所知的互联网将不再存在；FOSS 是一个美丽的系统，它不区分国界、种族、信仰和经济背景，赋予了每个人同样的权力。

FOSS 被破坏是因为其被一些用户滥用，FOSS 在这个过程中是受害者而不是罪魁祸首。主要的原因有几个，首要问题便是利润的最大化，要实现利润最大化，那么成本就要降到最低，所以公司在采用 FOSS 时并不会为其支付金钱，虽然不道德，但这并不违法。但话又说回来，一个 FOSS 该怎么定价呢，一个简单的 CSS 库、日志库甚至数据库是该用相同的定价还是不同的定价呢？

FOSS 并不是非黑即白。那么为什么还有那么多人会投入到 FOSS 的开发中呢，作者以自己为例，因为他喜欢它，他并不期望获得金钱回报，看到人们在使用自己所编写的软件时会让他感到高兴。这就是 FOSS 的美妙之处。

Tip

Linux 中的利用 gettimeofday() 函数和 struct timeval 来统计时间的方法如下：

#include <sys/time.h>

struct timeval start_timeval;
struct timeval end_timeval;

// 记录开始的时间
gettimeofday(&start_timeval, NULL);
// 要统计运行时间的代码
// 记录结束的时间
gettimeofday(&end_timeval, NULL);

// 计算时间差，得到的时间单位是 ms
float elapsed = (end_timeval.tv_sec - start_timeval.tv_sec) * 1000000.0
                  + end_timeval.tv_usec - start_timeval.tv_usec;

Share

本周分享一个网站：Programming Language and compiler Benchmarks

如标题所示，这个网站里记录统计了不同语言的在若干个相同程序下的编译和运行时间，主流的语言都有包括，如 C、C++、Java、JavaScript、Python 等等。

例如 C 语言，它还对比了相同程序在不同编译器下的表现，包括 gcc、clang 等。