C++中能否访问数组/vector的负索引？附相关代码疑问

我在解决“不选相邻元素的最大和”问题时，先写了递归解法，自己尝试用制表法实现却没成功。后来在网上找到一段能正常运行的代码，但发现里面有访问vector负索引的情况——按道理这应该触发错误，可代码居然跑起来了。

这段参考代码如下：

int maximumNonAdjacentSum(vector<int> &nums){
    int n = nums.size();
    vector<int> table(n+1,0);
    table[0] = nums[0];
    for(int i=1;i<=n; i++){
        table[i] = max(nums[i]+table[i-2],table[i-1]);
    }
    return table[n];
}

为什么负索引没报错？ #

这属于未定义行为，不是一定会崩溃。当i=1时，table[i-2]就是table[-1]，这时候程序会去访问vector起始地址之前的内存区域——如果这块内存刚好是进程可访问的（比如栈上的其他变量或者初始化的0值），程序就不会崩溃，但这种情况完全是碰运气，换个环境或者数据就可能直接崩溃，绝对不能依赖。

另外这段代码还有两个明显的错误：

• 当i=n时，nums[i]会访问nums[n]，但nums的有效索引是0到n-1，这也是越界访问，同样属于未定义行为。
• 初始化逻辑错误，table[0] = nums[0]没问题，但后续循环的起始条件没考虑边界情况。

修正后的正确制表法代码 #

int maximumNonAdjacentSum(vector<int> &nums){
    int n = nums.size();
    if(n == 0) return 0;
    if(n == 1) return nums[0];
    
    vector<int> table(n, 0);
    table[0] = nums[0];
    table[1] = max(nums[0], nums[1]);
    
    for(int i=2; i<n; i++){
        table[i] = max(nums[i] + table[i-2], table[i-1]);
    }
    return table[n-1];
}

如果想优化空间，可以不用整个vector，用两个变量滚动记录前两个状态：

int maximumNonAdjacentSum(vector<int> &nums){
    int n = nums.size();
    if(n == 0) return 0;
    
    int prev2 = nums[0];
    if(n == 1) return prev2;
    
    int prev1 = max(nums[0], nums[1]);
    for(int i=2; i<n; i++){
        int curr = max(nums[i] + prev2, prev1);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

修正说明 #

• 先处理空数组和单元素数组的边界情况，避免后续逻辑出错
• 初始化前两个状态，确保循环从i=2开始，不会出现i-2为负的情况
• 循环范围限定在0到n-1，避免访问nums的越界索引

内容的提问来源于stack exchange，提问作者Hiten Vats