NC501 牛牛的消消乐

1、首先对数组进行排序，使之成为递增顺序。
求一个数组的和sum，然后就是找到sum要减去的最大值。
这个最大值就是进行两次操作的时候要减去的数的总和。

2、因为数组是递增次数，因此我们如果要减去的元素是nums[ i ]，那么从下标 i 到下标n-1全部都可以减去。
减去的部分就是 nums[ i ] * (n-i)，因此我们可以遍历每个元素，减去1个之后，再对其排序再遍历减去第二个元素，找到能够减去的最大值。

3、最后sum减去最大值就是所求结果。

这里涉及一个Java数组的拷贝。
如果直接 res=nums; 的话，对res的修改会直接反应在nums上。
如果res=nums.clone();，则res是新地址的数组。

Java

import java.util.*;


public class Solution {
    
    public long minimumValueAfterDispel (int[] nums) {
        // write code here
        int n=nums.length;
        //求和
        int sum=0;
        for (int i=0; ivar1+var2 ? maxnum : var1+var2;
            }
            res=nums.clone(); //恢复辅助函数
        }
        return sum-maxnum;
    }
}

方法2：python

class Solution:
    def minimumValueAfterDispel(self , nums ):
        # write code here
        n=len(nums)
        res=list(nums)
        nums.sort()
        maxnum=0
        sumnum=sum(nums)
        for i in range(n):
            var1=nums[i]*(n-i)
            for j in range(i,n):
                res[j]-=nums[i]
            res.sort()
            for k in range(n):
                var2=res[k]*(n-k)
                maxnum=max(maxnum,var1+var2)
            res=list(nums)
        return sumnum-maxnum