LeetCode 1672：最富有客户资产问题——两行代码差异原因解析

这是LeetCode「最富有客户的资产总量」问题的两种解法，解法1在第三个测试用例中失败，解法2可通过所有测试用例，二者仅在max方法中的一行判断代码存在差异。

解法1（存在问题的代码） #

class Solution {
    public int maximumWealth(int[][] accounts) {    
        int[] money = new int[accounts.length];
        for(int i=0;i<accounts.length;i++){
            for(int j=0;j<accounts[i].length;j++){
                money[i] = money[i] + accounts[i][j];
            }
        }
        return max(money);
    }
    static int max(int[] money){
        int great = money[0];
        for(int i=1;i<money.length;i++){
            if(money[i]>money[i-1]){    // 此处为问题代码
                great = money[i];
            }
        }
        return great;
    }
}

解法2（正确的代码） #

class Solution {
    public int maximumWealth(int[][] accounts) {    
        int[] money = new int[accounts.length];
        for(int i=0;i<accounts.length;i++){
            for(int j=0;j<accounts[i].length;j++){
                money[i] = money[i] + accounts[i][j];
            }
        }
        return max(money);
    }
    static int max(int[] money){
        int great = money[0];
        for(int i=1;i<money.length;i++){
            if(money[i]>great){          // 此处为正确代码
                great = money[i];
            }
        }
        return great;
    }
}

差异分析 #

• 解法1的问题：判断条件money[i]>money[i-1]是将当前元素与前一个元素比较，而非与当前记录的全局最大值great比较。这种逻辑只能检测到数组中“比前一个元素大”的情况，无法保证找到真正的全局最大值。
  举个反例：如果money数组是[10, 5, 8]：

  1. 初始great为10；
  2. i=1时，5不大于前一个元素10，great保持10；
  3. i=2时，8大于前一个元素5，错误地将great更新为8；
     最终返回8，但实际最大值是10，导致结果错误。

• 解法2的正确性：判断条件money[i]>great是将当前元素与当前记录的全局最大值比较。每次遍历到更大的元素时，就更新great的值，无论数组元素的顺序如何，都能准确追踪到全局最大值，因此可以通过所有测试用例。

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