Pat 1045 quick sort

PAT1045

The problem is recursion , Use over Array record location i The difference from the maximum value of all previous data ( All the differences in this question refer to the current element minus other values ); After recording , Traverse from back to front , Find out the difference between the current data and the following minimum value ; If the difference between the current number and the front largest element is positive, it means that all the front elements of the current element are smaller than the current element , If the difference between the current element and the following smallest element is negative , Indicates that the current element is larger than all the following elements ; When both are satisfied , This element can be used as a primary element , Record current element position ;
The key to this problem is to find the recurrence relation , The difference between the current element and the previous maximum element can be obtained through analysis

 The current element  -  The former element  +  The difference between the previous element and the previous largest element   or   The current element  -  The former element 

The second possibility is when the current element is the maximum ( namely over[i - 1] > 0)

Similar to the difference of the following smallest element ;

#include<cstdio>
const int maxn = 100010;
int over[maxn] = {
    0};	// The difference between the current position and the maximum element 
int main() {
    
	int n, arr[maxn] = {
    0};
	scanf("%d", &n);
	for(int i = 0; i < n; i++) {
    
		scanf("%d", &arr[i]);
	}
	for(int i = 0; i < n; i++) {
    
		if(i > 0) {
    
			over[i] = arr[i] - arr[i - 1] + over[i - 1];
		}
		if(over[i - 1] > 0) {
    		// If the previous one is the maximum , That is, the difference between the previous maximum value and the previous maximum value is positive 
			over[i] = arr[i] - arr[i - 1];
		}
	}
	int low = 0, ans[n] = {
    -1}, index = 0;		// The difference between the current element and the following smallest element 
	for(int i = n - 1; i > -1; i--) {
    
		if(i == n - 1) {
    
			low = 0;
		} else if(low < 0) {
    	// If the previous one is the minimum 
			low = arr[i] - arr[i + 1];
		} else {
    
			low = arr[i] - arr[i + 1] + low; 
		}
		if(over[i] >= 0 && low <= 0) {
    
			ans[index++] = i;
		}
	}
	printf("%d\n", index);
	for(int i = index - 1; i > -1; i--) {
    
		printf("%d", arr[ans[i]]);
		if(i > 0) {
    
			printf(" ");
		}
	}
    printf("\n");
	return 0;
}