Java Dynamic Programming
IntuitionUse dynamic programming to count how many times each num in nums contribute to the sum of min or maxApproachSort array nums, so the new picked num must
# Intuition
Use dynamic programming to count how many times each num in nums contribute to the sum of min or max

# Approach
Sort array nums, so the new picked num must be max of the sequence.

loop nums, and calculate the number of subsequence which has length(1-Math.min(i+1,k))
count[i][j] : how many subsequence has length j and ends at index i of nums
preSum[i][j]: until index i of array nums, how many subsequences which has length less/equal to j;

at each step, 
calculate count[i][j] based on preSum[i-1][j-1](previous count of all subsequences which has length less than j, then we can append nums[i] to the existing subsequence to create the new subsequence)

the new created subsequences's last num is nums[i], and it's the max of each subsequence, so the final sum add nums[i]*count[i][j]

calculate preSum[i][j], add the new calculated count[i][j] to preSum[i-1][j-1];

Then we loop from right to left, to calculate how many times each nums[i] contribute to the final result as min of the subsequence



# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
O(nk)
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
O(nk)

# Code
```java []
class Solution {
    public int minMaxSums(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length, mod = 1000000007;
        long sum = 0;
        long[][] count = new long[n][k+1];
        long[][] preSum = new long[n][k+1];
        for(int i=0;i<n;i++){
            for(int j=1;j<=Math.min(i+1,k);j++){
                if(j== 1){
                    count[i][j] = 1;
                }else{
                    count[i][j] = (i>0?preSum[i-1][j-1]:0);
                }
                
                sum = (sum + nums[i]*count[i][j])%mod;
                preSum[i][j] = ((i>0?preSum[i-1][j]:0) + count[i][j])%mod;
            }
        }
        count = new long[n][k+1];
        long[][] suffixSum = new long[n][k+1];
        for(int i=n-1;i>=0;i--){
            for(int j=1;j<=Math.min(n-i,k);j++){
                if(j==1){
                    count[i][j] = 1;
                }else{
                    count[i][j] = (i<n-1?suffixSum[i+1][j-1]:0);
                }
                sum = (sum + nums[i]*count[i][j])%mod;
                suffixSum[i][j] = ((i<n-1?suffixSum[i+1][j]:0) + count[i][j])%mod;
            }
        }
        return (int)sum;
    }
}
```
['Dynamic Programming', 'Java']