2104.子数组范围和

解法一：暴力法
解法二：DP

给你一个整数数组 nums 。 nums 中，子数组的范围是子数组中最大元素和最小元素的差值。
返回 nums 中所有子数组范围的和。
子数组是数组中一个连续非空的元素序列。
示例 1：

输入：nums = [1,2,3]
输出：4
解释：nums 的 6 个子数组如下所示：
[1]，范围 = 最大 - 最小 = 1 - 1 = 0
[2]，范围 = 2 - 2 = 0
[3]，范围 = 3 - 3 = 0
[1,2]，范围 = 2 - 1 = 1
[2,3]，范围 = 3 - 2 = 1
[1,2,3]，范围 = 3 - 1 = 2
所有范围的和是 0 + 0 + 0 + 1 + 1 + 2 = 4

示例 2：

输入：nums = [1,3,3]
输出：4
解释：nums 的 6 个子数组如下所示：
[1]，范围 = 最大 - 最小 = 1 - 1 = 0
[3]，范围 = 3 - 3 = 0
[3]，范围 = 3 - 3 = 0
[1,3]，范围 = 3 - 1 = 2
[3,3]，范围 = 3 - 3 = 0
[1,3,3]，范围 = 3 - 1 = 2
所有范围的和是 0 + 0 + 0 + 2 + 0 + 2 = 4

示例 3：

输入：nums = [4,-2,-3,4,1]
输出：59
解释：nums 中所有子数组范围的和是 59

提示：

1 <= nums.length <= 1000
-10^9 <= nums[i] <= 10^9
解法一：暴力法

func subArrayRanges(nums []int) int64 {
    n := len(nums)
    var res int64
    var max, min int
    for i := 0; i < n-1; i++ {
        max = nums[i]
        min = nums[i]
        for j := i + 1; j < n; j++ {
            if max < nums[j] {
                max = nums[j]
            }
            if min > nums[j] {
                min = nums[j]
            }
            res += int64(max - min)
        }
    }
    return res
}

解法二：DP

func subArrayRanges(nums []int) int64 {
  type pair struct {
    max, min int
  }
  n := len(nums)
  dp:= make([][]pair,n)
  for i := 0; i < n; i++ {
    dp[i] = make([]pair, n)
    for j := 0; j< n; j++ {
      dp[i][j] = pair{max: math.MinInt64, min:math.MaxInt64}
    }
  }
  var res int64
  for i:=0; i<n;i++ {
    for j:=i;j<n;j++ {
      if i == j {
        dp[i][j] = pair{max: nums[i], min: nums[i]}
      } else {
        dp[i][j] = pair{max: max(dp[i][j-1].max, nums[j]), min: min(dp[i][j-1].min, nums[j])}
      }
      res += int64(dp[i][j].max - dp[i][j].min)
    }
  }
  return res
}

func max(x, y int)int {
  if x > y {
    return x
  }
  return y
}

func min (x, y int)int {
  if y > x {
    return x
  }
  return y
}

解法一：暴力法

解法二：DP