贪心策略：请你计算i×arr[i]的累加和最大值

提示：从本文开始，咱们来说贪心策略系列文章！！

贪心策略在互联网大厂的招聘笔试和面试中的地位！！！在笔试中考贪心，而面试不考贪心。

（1）贪心在笔试中：75%的考题都是贪心策略，为啥呢，一方面考你的聪明程度，另一方面，考你的代码编写能力；所以我参加过的笔试证明了这一点，往往大厂给你三个算法题，第1道题一定是贪心，排序结合的算法题，你需要懂点脑子，了解一下排序和堆啥的数据结构，还得会点贪心技巧，才能设计出来；
（2）面试不怎么考贪心策略，为什么？因为面试考你的是算法的优化能力，所以如果给你贪心的话，你一下子想到了解决方案，也不谈什么优化的事情，没意义，所以不考贪心。
（3）你必须要认识到：最简单的是国内的面试过程（嘴说的事情，都好办），难度中上等的是国外的笔试面试，最难的国内的算法笔试。 那么，你一定要明白，最难的还是国内的算法笔试题！！！因此要多练，多学，多见题，多思考，多总结，才能拿下。

文章目录

• 贪心策略：请你计算i×arr[i]的累加和最大值
• • @[TOC](文章目录)
• 题目
• 一、审题
• 总结

题目

给你一个数组arr， 各个元素均大于，请你计算i×arr[i]的累加和最大值

一、审题

示例：比如：
arr = 2 1
i 1 2
乘积累加和为21+12=4

咱们要保证iarr[i]最大，那最好是，**大数大的数，能得到更大的数** ——这就是此题的贪心之处！！

你排序一下arr呢？
arr = 1 2
i 1 2
乘积累加和为11+22=5
故最大值是5

手撕代码搞定：

public class maxSumimultiplyarri {
    //给你一个数组arr， 各个元素均大于，请你计算i×arr[i]的累加和最大值
    public static int maxSumImultiplyArri(int[] arr){
        if (arr == null || arr.length == 0) return 0;

        int sum = 0;
        Arrays.sort(arr);//升序

        for (int i = 0; i < arr.length; i++) {
            sum += i * arr[i];
        }

        return sum;
    }

    public static void test(){
        int[] arr = {0,2,1};
        System.out.println(maxSumImultiplyArri(arr));
    }

    public static void main(String[] args) {
        test();
    }

结果：5

贪心这玩意，看多了，练习多了，见多识广，敏感度就培养上来了

那你的方法对不对呢？
你就整一个暴力解，验证一下，
当然，你做题吗不是，那就将代码提交到大厂的后台，它不一会就给你验证了，如果OK：100%通过AC
或者10%，20%，80%，说明你的代码有问题，要么边界条件没有卡对，要么就是逻辑出错了
要么就是压根你这贪心算法就是错的。

那你重新设计呗！

总结

提示：重要经验：

1）贪心策略只在笔试中考，面试不考
2）贪心策略的敏感度，需要大量的练习，见多识广总结出来经验。
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。