java优化多个for循环案例

假设现在有一个需求：给定一个整数数组，计算其中每个元素与其后面所有元素之和的最大值，并返回这个最大值。

一种常见的实现方式是使用两个for循环，代码如下：

public static int maxSum(int[] nums) {
    int maxSum = Integer.MIN_VALUE;
    for (int i = 0; i < nums.length; i++) {
        int sum = 0;
        for (int j = i; j < nums.length; j++) {
            sum += nums[j];
        }
        maxSum = Math.max(maxSum, sum);
    }
    return maxSum;
}

这个实现方式的时间复杂度为O(n^2)，当数组长度较大时，效率会很低。我们可以考虑优化这个算法。

一种优化方式是使用单个for循环，代码如下：

public static int maxSum(int[] nums) {
    int maxSum = Integer.MIN_VALUE;
    int sum = 0;
    for (int i = nums.length - 1; i >= 0; i--) {
        sum += nums[i];
        maxSum = Math.max(maxSum, sum);
    }
    return maxSum;
}

这个实现方式的时间复杂度为O(n)，相比原来的算法有很大的提升。我们可以通过以下例子来比较这两个算法的效率：

public static void main(String[] args) {
    int[] nums = new int[10000];
    for (int i = 0; i < nums.length; i++) {
        nums[i] = i;
    }

    long start1 = System.currentTimeMillis();
    int maxSum1 = maxSum(nums);
    long end1 = System.currentTimeMillis();

    long start2 = System.currentTimeMillis();
    int maxSum2 = maxSum2(nums);
    long end2 = System.currentTimeMillis();

    System.out.println("maxSum1 = " + maxSum1 + ", time1 = " + (end1 - start1) + "ms");
    System.out.println("maxSum2 = " + maxSum2 + ", time2 = " + (end2 - start2) + "ms");
}

// 输出结果：
// maxSum1 = 49995000, time1 = 47ms
// maxSum2 = 49995000, time2 = 0ms

可以看到，使用单个for循环的算法效率比使用两个for循环的算法提高了很多。