[toc]

在《算法导论》中举了买股票和割铁棒的例子来说明动态规划和贪心算法的主体思想。

贪心算法：总是做出在当前看来最好的情况。（不是整体最优的）

1. 问题及答案

---

先抛出一个问题，类似于《算法导论》中的股票问题。

1.1 问题

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
简单的一句话概括，就是找一个数组中拥有最大和的子数组，返回其和。

答案（不唯一）只有6行，可以说是非常简洁，且便于理解了。

1.2 答案

/* 
 *@lucastan 
 */
int maxSubArray(vector<int> &nums) {
    int ans = nums[0], i, sum = 0;
    for(i = 0; i < nums.size(); i++){
        sum += nums[i];
        ans = max(sum, ans);
        sum = max(sum, 0);
    }
    return ans;
}

2. 解题思路

---

读完问题，我们立刻就能想到的是从头开始加，总能枚举出来一个。

这个想法可以说是非常朴实了，但是……我们还是继续思考吧，第二反应就是贪心算法了（如果你能想到动态规划的思想，也不错啊，可以类似的求解）。

首先我们要说，贪心算法是什么？

总是找到一个在当前看来最优的解。

然后，我们现在要求的是什么？

数组中拥有最大和的子数组。

这样一来，目标就明确了，我们肯定是需要遍历数组的，不然怎么能确定我们考虑到了数组中所有元素呢？

明确了目标，我们结合贪心算法的定义，提出下一个问题，我们怎么确定现在的子数组元素的和到目前为止是最大的呢？

与在添加了下一个元素之前的数组进行比较。

那万一我们加到数组的某一个位置的时候，出现了和为负的情况……

笨啊，一旦加到某个元素出现和为负的情况，我们就应该舍弃前面的所有元素，然后在下一个元素处重新开始求和。如果等于零，那么我们就要从这个元素开始重新求和。
另外，不要钻最大子数组在中间的这一种情况的牛角尖，除非在计算时数组前面的元素和小于等于零，否则我们在这个代码里，永远会得到[0...x]（x代表子数组的最后一个元素序号，[0...x]难道不是他的子数组吗？就算我们最后得到数组本身，他也是该数组的子数组）。

3. 一点想法

---

文章看到这里，可能就有人发现了，这个问题并不是真的应用了贪心算法，我们只是借来了贪心算法一点点的思想，然后就得到了问题的解答。

（完整的贪心算法思想在这里是不能应用的，如果题目不要求子数组连续，那么倒是可以完整的应用贪心算法思想，但这样一来问题也就失去了意义。）

看了标题和开头的一点点胡言乱语，你是不是真的以为我要讲贪心算法了，哼，天真。

装完逼就跑，真刺激