2023-11-22：用go语言，给你一个长度为 n 下标从 0 开始的整数数组 nums。
它包含 1 到 n 的所有数字，请你返回上升四元组的数目。
如果一个四元组 (i, j, k, l) 满足以下条件，我们称它是上升的：
0 <= i < j < k < l < n 且
nums[i] < nums[k] < nums[j] < nums[l] 。
输入：nums = [1,3,2,4,5]。
输出：2。
来自左程云。
答案2023-11-22：
go代码用灵捷3.5编写。
rust代码用讯飞星火编写。
c++的代码用天工编写。
灵捷3.5本来用起来还可以，但有次数限制，故放弃。
大体过程如下：
算法1：countQuadruplets1
1.初始化变量：n为数组长度，ans为结果计数器，dp为动态规划数组。
2.遍历数组，从第二个元素开始（下标为1）：
a.初始化计数器cnt为0。
b.遍历当前元素之前的所有元素（下标小于当前元素的下标），如果当前元素大于前一个元素，则将dp[j]加到ans上，并将cnt加1。
c.再次遍历当前元素之前的所有元素（下标小于当前元素的下标），如果当前元素大于前一个元素，则将cnt加到dp[j]上；否则，将dp[j]加上cnt的整数值。
3.返回ans作为结果。
算法2：countQuadruplets2
1.初始化变量：n为数组长度，ans为结果计数器，dp为动态规划数组。
2.遍历数组，从第二个元素开始（下标为1）：
a.初始化计数器cnt为0。
b.遍历当前元素之前的所有元素（下标小于当前元素的下标），如果当前元素大于前一个元素，则将dp[j]加到ans上，并将cnt加1；否则，将dp[j]加上cnt的整数值。
3.返回ans作为结果。
总的时间复杂度：两种算法的时间复杂度都是O(n^2)，因为需要两层循环遍历数组。
总的额外空间复杂度：两种算法的空间复杂度都是O(n)，因为需要使用一个长度为n的动态规划数组dp。
go完整代码如下：
package main
import "fmt"
func countQuadruplets1(nums []int) int64 {
n := len(nums)
var ans int64
dp := make([]int64, n)
for l := 1; l < n; l++ {
cnt := 0
for j := 0; j < l; j++ {
if nums[j] < nums[l] {
ans += dp[j]
}
}
cnt = 0
for j := 0; j < l; j++ {
if nums[j] < nums[l] {
cnt++
} else {
dp[j] += int64(cnt)
}
}
}
return ans
}
func countQuadruplets2(nums []int) int64 {
n := len(nums)
var ans int64
dp := make([]int64, n)
for l := 1; l < n; l++ {
cnt := 0
for j := 0; j < l; j++ {
if nums[j] < nums[l] {
ans += dp[j]
cnt++
} else {
dp[j] += int64(cnt)
}
}
}
return ans
}
func main() {
nums := []int{1, 3, 2, 4, 5}
fmt.Println(countQuadruplets1(nums))
fmt.Println(countQuadruplets2(nums))
}
rust完整代码如下：
fn count_quadruplets1(nums: Vec<i32>) -> i64 {
let n = nums.len();
let mut ans = 0;
let mut dp = vec![0; n];
for l in 1..n {
let mut cnt = 0;
for j in 0..l {
if nums[j] < nums[l] {
ans += dp[j];
cnt += 1;
} else {
dp[j] += cnt;
}
}
}
ans as i64
}
fn count_quadruplets2(nums: Vec<i32>) -> i64 {
let n = nums.len();
let mut ans = 0;
let mut dp = vec![0; n];
for l in 1..n {
let mut cnt = 0;
for j in 0..l {
if nums[j] < nums[l] {
ans += dp[j];
cnt += 1;
} else {
dp[j] += cnt;
}
}
}
ans as i64
}
fn main() {
let nums = vec![1, 3, 2, 4, 5];
println!("count_quadruplets1: {}", count_quadruplets1(nums));
let nums = vec![1, 3, 2, 4, 5];
println!("count_quadruplets2: {}", count_quadruplets2(nums));
}
c++完整代码如下：
#include <iostream>
#include <vector>
using namespace std;
long long countQuadruplets1(vector<int>& nums) {
int n = nums.size();
long long ans = 0;
vector<long long> dp(n, 0);
for (int l = 1; l < n; l++) {
for (int j = 0; j < l; j++) {
if (nums[j] < nums[l]) {
ans += dp[j];
}
}
int cnt = 0;
for (int j = 0; j < l; j++) {
if (nums[j] < nums[l]) {
cnt++;
}
else {
dp[j] += cnt;
break;
}
}
}
return ans;
}
long long countQuadruplets2(vector<int>& nums) {
int n = nums.size();
long long ans = 0;
vector<long long> dp(n, 0);
for (int l = 1; l < n; l++) {
int cnt = 0;
for (int j = 0; j < l; j++) {
if (nums[j] < nums[l]) {
ans += dp[j];
cnt++;
}
else {
dp[j] += cnt;
}
}
}
return ans;
}
int main() {
vector<int> nums = { 1, 3, 2, 4, 5 };
cout << countQuadruplets1(nums) << endl;
cout << countQuadruplets2(nums) << endl;
return 0;
}
