Application of C++ prefix sum algorithm: statistical ascending quadruples

Basic knowledge points involved in this article

C++ algorithm: principles, source code and test cases of prefix sum, prefix product, prefix XOR including course videos

Title

Given an integer array nums of length n with subscripts starting from 0, which contains all numbers from 1 to n, please return the number of ascending quadruples.
We say a quadruple (i, j, k, l) is ascending if it satisfies the following conditions:
0 <= i < j < k < l < n and
nums[i] < nums[k] < nums[j] < nums[l].
Example 1:
Input: nums = [1,3,2,4,5]
Output: 2
explain:

When i = 0, j = 1, k = 2 and l = 3, there is nums[i] < nums[k] < nums[j] < nums[l].
When i = 0, j = 1, k = 2 and l = 4, there is nums[i] < nums[k] < nums[j] < nums[l].
There are no other quadruples, so we return 2 .
Example 2:
Input: nums = [1,2,3,4]
Output: 0
Explanation: There is only one quadruple i = 0, j = 1, k = 2, l = 3, but nums[j] < nums[k], so we return 0.
Parameter range:
4 <= nums.length <= 4000
1 <= nums[i] <= nums.length
All numbers in nums are different from each other, and nums is a permutation.

Easy to understand

Analysis

The first-level loop enumerates j, and the second-level loop enumerates k. Time complexity O(n*n). Between passing and failing, using vector will not pass, but using int** will barely pass. In two steps:


First step	Find the sum of prefixes
The second step	Enumerate j and k

Core code

class Solution {
public:
long long countQuadruplets(vector & nums) {
m_c = nums.size();
int** vSum = new int*[m_c + 1];//vSum[i][j]: The number of items less than or equal to i in nums[0,j)
for (int i = 1; i <= m_c; i + + )
{//Calculate the number less than i
vSum[i] = new int[m_c + 1];
vSum[i][0] = 0;
for (int j = 0; j < m_c; j + + )
{
vSum[i][j + 1] = vSum[i][j] + (nums[j] <= i);
}
}
long long llRet = 0;
for (int j = 1; j < m_c; j + + )
{
for (int k = j + 1; k + 1 < m_c; k + + )
{
if (nums[j] < nums[k])
{
continue;
}
//nums[i] range: the number in nums[0,j) less than or equal to nums[k]
const long long lessNumK = vSum[nums[k]][j];
//nums[k + 1,m_c) is greater than nums[j]
const long long moreNumJ = m_c – (k + 1) – (vSum[nums[j]][m_c]- vSum[nums[j]][k + 1]);
llRet + = lessNumK * moreNumJ;
}
}
return llRet;
}
int m_c;
};

Test cases

template
void Assert(const vector & amp; v1, const vector & amp; v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i + + )
{
assert(v1[i] == v2[i]);
}
}

template
void Assert(const T & t1, const T & t2)
{
assert(t1 == t2);
}

int main()
{
Solution slug;
vectornums;
long long res;
nums = { 1, 3, 2, 4, 5 };
res = slu.countQuadruplets(nums);
Assert(2LL, res);
nums = { 1, 2,3,4 };
res = slu.countQuadruplets(nums);
Assert(0LL, res);
nums = { 4,3,2,1 };
res = slu.countQuadruplets(nums);
Assert(0LL, res);
nums = { 4,3,2,6,5,1 };
res = slu.countQuadruplets(nums);
Assert(0LL, res);
nums = { 1,3,2,4 };
res = slu.countQuadruplets(nums);
Assert(1LL, res);
nums = { 2,1,4,3,5 };
res = slu.countQuadruplets(nums);
Assert(2LL, res);
nums.clear();
for (int i = 0; i < 4000; i + + )
{
nums.emplace_back(i + 1);
}
res = slu.countQuadruplets(nums);
Assert(0LL, res);
//CConsole::Out(res);
}

Performance is slightly stronger

Analysis

The first level of loop enumerates l or k; the second level of loop enumerates j. The time complexity is O(n*n), the code is much simpler and can be passed easily.

Variable explanation


llRet	All matches Conditional quaternary ancestor
iLessLK	The number in nums[0,j) that is less than nums[i]
m_v132[j]	The number of i, j, k in nums[0,i)

Core code

class Solution {<!-- -->
public:
long long countQuadruplets(vector<int> & amp; nums) {<!-- -->
m_c = nums.size();
long long llRet = 0;
vector<long long> m_v132(m_c);//132
for (int lk = 0; lk < m_c; lk + + )
{<!-- -->
int iLessLK = 0;
for (int j = 0; j < lk; j + + )
{<!-- -->
if (nums[j] < nums[lk])
{<!-- -->
iLessLK + + ;
llRet + = m_v132[j];
}
else
{<!-- -->
//iLessLK represents the number in [0, j) that is less than nums[lk]. Assume that its index is i, then nums[i] < nums[lk], nums[j] < nums[lk], so i j lk, consistent with The first three numbers i,j,k
m_v132[j] + = iLessLK;
}
}
}
return llRet;
}
int m_c;
};

Old code from February

class Solution {
public:
long long countQuadruplets(vector & nums) {
m_c = nums.size();
//vLeft[i][m] represents nums[i] and the previous elements, the number less than or equal to m + 1
int vLeft[4000][4000] = { 0 };
{
for (int i = 0; i < m_c; i + + )
{
if (i > 0)
{
memcpy(vLeft[i], vLeft[i – 1], sizeof(vLeft[0]));
}
for (int j = nums[i] – 1; j < m_c; j + + )
{
vLeft[i][j] + + ;
}
}
}
long long llRet = 0;
for (int j = 1; j + 1 < m_c; j + + )
{
for (int k = j + 1; k + 1 < m_c; k + + )
{
if (nums[j] <= nums[k])
{
continue;
}
const int iLeft = vLeft[j – 1][nums[k] – 1];
const int iRight = nums[j] – vLeft[k][nums[j] – 1];
llRet + = vLeft[j – 1][nums[k] – 1] * (nums.size() – k – 1 – iRight);
}
}
return llRet;
};
int m_c;
};

Extended reading

Video course

Effective learning: clear goals, timely feedback, stretching zone (appropriate difficulty), you can learn simple courses first, please go to CSDN Academy and listen to the explanation of Baiyin Lecturer (that is, I).
https://edu.csdn.net/course/detail/38771

how fast do you want

A battle has quickly formed. To share the worries of your boss, please learn C# onboarding training, C++ onboarding training and other courses.
https://edu.csdn.net/lecturer/6176

Related downloads

If you want to know the superior learning algorithm, please download the doc version of “Algorithm Book When You Hear the Defects”
https://download.csdn.net/download/he_zhidan/88348653

I am full of positive energy and say it to everyone
It is a good wish to be happy when you hear the flaws. Discover problems early, correct them early, and save your boss money.
The origin of the Mohist name: everything is recorded in Mohism.
Algorithms will eventually rule the universe, and we will rule the algorithms. “The Complete Book of Xi Que”

Test environment

Operating system: win7 Development environment: VS2019 C++ 17
Or operating system: win10 open

Development environment: VS2022 C++ 17