将变量打印到控制台显示意外行为

Question

以下代码尝试打印给定 ArrayList C 的所有子数组中的最大和，前提是该和不大于给定变量 B 的值。

import java.util.*;
public class Main
{
    public static void main(String[] args) {
        ArrayList <Integer> C=new ArrayList <> ();
        Collections.addAll(C,7,1,8,5,8,5,3,3,5);
        int B=999;
        int maxSum=0;
        // int TheRealMax=0;
        for(int i=0;i<C.size();i++){
            for(int j=i;j<C.size();j++){
                
                for(int k=i;k<=j;k++){
                    
                        maxSum+=C.get(k);
                        if(maxSum>B)
                            maxSum-=C.get(k);
                    
                }
                
            }
        }
        System.out.println(maxSum);
    }
}

现在我知道代码是错误的并且无法正常工作，并且我不需要正确的代码。
我真正困惑的是打印到控制台的值（maxSum 的值）。我观察到以下情况：对于 B 的“小值”，取 99，打印的值（maxSum）是 B 本身的值。对于 B 的“较大值”，例如 999 甚至 9784535 等，您明白了，显示的值是“843”。

奇怪的是 maxSum 似乎以某种方式获取了 B 的值，即使代码中的两个变量之间除了条件检查之外没有任何链接。我也不知道数字 843 到底是从哪里来的。
我想知道的是，maxSum 从哪里得到这些值？

Answer 1

您好，我发现您的代码存在一些问题 -

1. 每次子数组迭代后，您不会重置

   maxSum

2. 时间复杂度 -

   O(n^3)

修复

import java.util.*;
public class Main
{
    public static void main(String[] args) {
        ArrayList <Integer> C=new ArrayList <> ();
        Collections.addAll(C,7,1,8,5,8,5,3,3,5);
        int B=999;
        int maxSum=0;
        // int TheRealMax=0;
        for(int i=0;i<C.size();i++){
            for(int j=i;j<C.size();j++){
                int subArraySum = 0; //This will hold the Sum of each subarray
                for(int k=i;k<=j;k++){
                        subArraySum+=C.get(k);
                        if(subArraySum>B){
                            subArraySum-=C.get(k);
                            break; //If sum exeeds the B break the loop
                        }
                    
                }
                if(subArraySum>maxSum)
                    maxSum=subArraySum;
            }
        }
        System.out.println(maxSum);
    }
}

但是这段代码的时间复杂度为

O(n^3)

，如果输入大小很大，可能会导致问题，我强烈建议使用 Kadane 的算法，因为它会将时间复杂度降低到

O(n)

，将空间复杂度降低到

O(1)