文章

85

粉丝

253

获赞

1

访问

29.2k

头像
2025年(408)计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年12月18日 16:13
阅读数 104

### (1)算法的基本设计思想
要高效计算`res[i]`(即`A[i]`与`A[j]`(`i≤j≤n-1`)乘积的最大值),核心是**避免暴力遍历(O(n²)复杂度)**,利用“从后向前遍历+动态维护极值”的思路优化:
1. **遍历方向**:从数组末尾(`j = n-1`)向前遍历到起始(`j = 0`),因为`res[i]`依赖`i`右侧(`j≥i`)的元素,反向遍历可复用已计算的右侧信息。
2. **动态维护极值**:遍历过程中,实时记录当前位置`j`右侧(含`j`)的**最大值`max_val`** 和**最小值`min_val`**。原因是:`A[i]`与右侧元素的乘积最大值,可能来自`A[i]×max_val`(两者同号),也可能来自`A[i]×min_val`(两者异号,如负负得正且绝对值更大)。
3. **计算`res[i]`**:对每个`i`,用当前`A[i]`分别与`max_val`、`min_val`相乘,取两者中的较大值作为`res[i]`;随后更新`max_val`和`min_val`(纳入`A[i]`,确保后续左侧`i-1`的计算能用到`i`及右侧的极值)。


### (2)C语言实现代码
```c
void calMulMax(int A[], int res[], int n) {
    // 异常处理:数组为空或长度为0时直接返回
    if (n <= 0 || A == NULL || res == NULL) {
        return;
    }
    
    // 初始化:从数组末尾开始,初始max_val和min_val均为A[n-1](仅含最后一个元素)
    int max_val = A[n-1];
    int min_val = A[n-1];
    // res[n-1]:j只能等于n-1,乘积即A[n-1]×A[n-1]
    res[n-1] = A[n-1] * A[n-1];
    
    // 从倒数第二个元素(i = n-2)向前遍历到第一个元素(i = 0)
    for (int i = n - 2; i >= 0; i--) {
        // 计算当前A[i]与右侧max_val、...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发