腾讯元宝发红包直接把服务器干崩了。。

2月1日的时候，腾讯旗下的app元宝发文称：10亿现金红包开抢，这个套路感觉和前几年的微信红包和支付宝红包有点类似。不过蚊子腿也是肉，虽然抢到的少，但还是有很多人参与。我手机本来就有这个app，顺便也参与了，也就几块钱，每天有5次抽奖的机会。

可能是由于参与的人太多，2月2日凌晨，元宝没有顶住压力，还是崩了，用户在使用过程中多次出现“已暂停生成”字眼。针对该问题，腾讯回应称，因活动参与热度超出预期引发造成故障，瞬时流量激增，部分服务出现短暂不稳定，目前已经恢复。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第3010题：将数组分成最小总代价的子数组 I，难度是简单。

给你一个长度为 n 的整数数组 nums， 一个数组的代价是它的第一个元素。比方说，[1,2,3] 的代价是 1 ，[3,4,1] 的代价是 3 。

你需要将 nums 分成 3 个连续且没有交集的子数组。请你返回这些子数组的最小代价总和 。

示例1：

输入：nums = [1,2,3,12] 输出：6 解释：最佳分割成 3 个子数组的方案是：[1] ，[2] 和 [3,12] ，总代价为 1 + 2 + 3 = 6 。 其他得到 3 个子数组的方案是： [1] ，[2,3] 和 [12] ，总代价是 1 + 2 + 12 = 15 。 [1,2] ，[3] 和 [12] ，总代价是 1 + 3 + 12 = 16 。

示例2：

输入：nums = [10,3,1,1] 输出：12 解释：最佳分割成 3 个子数组的方案是：[10,3] ，[1] 和 [1] ，总代价为 10 + 1 + 1 = 12 。 12 是所有分割方案里的最小总代价。

• 3 <= n <= 50

• 1 <= nums[i] <= 50

问题分析

这题说的是把数组分成3个不重叠的子数组，然后求这3个子数组代价之和的最小值，每个子数组的代价就是它的第一个元素。

很明显第一个子数组的代价就是原数组中第一个元素，那么后面两个子数组的代价是多少呢？实际上就是原数组中除了第一个元素以外，剩余元素中最小的两个元素。

为什么是这样的呢？我们来举个例子，比如数组[a,b,c,d,e,f,g,h,i,j]，除了第一个元素以外，剩余的两个最小值假如分别是e和h，我们可以把原数组分为[a,b,c,d]，[e,f,g]，[h,i,j]，它们总的代价之和就是原数组中第一个元素a和剩余元素中最小的两个e和h之和。

JAVA：

                      public int minimumCost(int[] nums) {
    // first和second是除了数组中第一个元素以外，剩余元素中最小的两个。
    int first = Integer.MAX_VALUE;
    int second = Integer.MAX_VALUE;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] <= first) {
            second = first;
            first = nums[i];
        } else if (nums[i] < second) {
            second = nums[i];
        }
    }
    return nums[0] + first + second;
}

C++：

                      public:
    int minimumCost(vector &nums) {
        // first和second是除了数组中第一个元素以外，剩余元素中最小的两个。
        int first = INT_MAX;
        int second = INT_MAX;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] <= first) {
                second = first;
                first = nums[i];
            } elseif (nums[i] < second) {
                second = nums[i];
            }
        }
        return nums[0] + first + second;
    }

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解900多题，对算法题有自己独特的解题思路和解题技巧。