文章
85
粉丝
253
获赞
1
访问
29.2k
### (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、...
登录后发布评论
暂无评论,来抢沙发