1、解题思路

将数组按从大到小的顺序排列，i<=j，那么以nums[i]开始，nums[j]结尾，i----j中的任意数，组成的排列，其英雄力量都是nums[i]*nums[i]*nums[j]；

• 若i==j，则只有一种排列组合；
• 若i！=j，设n=j-i-1（表示i----j中的数据的个数），排列组合总共有Cn0+Cn1+......+Cnn=2^n个

因此可以设置双重循环遍历数组，来计算总的英雄的力量。

for(int i=0;i<n;i++){
   for(int j=i;j<n;j++){
      if(i==j){
         sum+=nums[i]*nums[i]*nums[i];
      }else{
         sum+=nums[i]*nums[i]*nums[j]*pow(2,j-i-1);
      }
   }
}

时间复杂度为O(n^2)，会超时。

2、算法优化

双重循环的内部的一层循环，实际上是在计算以nums[i]为最大值的所有排列组合的最小值的和dp[i]，则sum=sum+nums[i]*nums[i]*dp[i]；

以nums[i]为最大值的所有排列组合：

• 1、只有nums[i]一个值
• 2、nums[i+1]........nums[n-1]的任意排列组合，加上nums[i]构成的新组合

其中2，nums[i+1]........nums[n-1]的任意排列组合，可以将他们分为这样几类：以nums[i+1]为最大值的排列组合、......、以nums[n-1]为最大值的排列组合。

因此dp[i]=nums[i]+

class Solution {
public:
    static bool cmp(int a,int b){
        return a>b;
    }
    int sumOfPower(vector<int>& nums) {
        sort(nums.begin(),nums.end(),cmp);
        int n=nums.size();
        long long int sum=0;
        long long int mod=1000000007;
        vector<int> dp(nums.size());
        dp[n-1]=nums[n-1];
        sum=(long long int)nums[n-1]*nums[n-1]%mod*dp[n-1]%mod;
        for(int i=n-2;i>=0;i--){
            dp[i]=((long long int)nums[i]+2*dp[i+1]-nums[i+1])%mod;
            sum=sum+((long long int)nums[i]*nums[i]%mod*dp[i])%mod;
            sum%=mod;
        }
        return sum;
    }
};