2025年408数据结构真题(二刷)

//2025年真题

//这道题要计算a[i]*a[j]的最大值，可以分为正数乘以正数和负数乘以负数来讨论：
//题目还要求i<=j，这就可以设置一个辅助数组b[n]从后往前保存对应位置正数最大的值，和负数最小的值

void calmulmax(int a[],int res[],int n){
    int b[n];
    int max = INT_MIN;  //max记录这个位置a[i]到a[n-1]的最大整数；
    int min = INT_MAX;  //min记录这个位置a[i]到a[n-1]的最小的负数；
for (int i = n-1;i >= 0;i--) {
if (a[i] >= 0){
if (a[i] > max){
                max = a[i];
                b[i] = max;
            } else{
                b[i] = max;
            }
        } else {
if (a[i] < min){
                min = a[i];
                b[i] = min;
            } else{
                b[i] = min;
            }
        }
    }
for (int i = 0; i < n; ++i) {
        res[i] = a[i] * b[i];
    }
}