Java求数组的子数组之和的最大值

[java]代码库

// 输入一个整形数组，数组里有正数也有负数。
// 数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
// 求所有子数组的和的最大值。要求时间复杂度为O(n)。
public class Test
{
    static int[] arr =
    {
            1, -2, 3, 10, -4, 7, 2, -5
    };// 需要求的数组
    static int maxIndex = arr.length - 1;// 数组的最大下标

    public static void main(String[] args)
    {
        findMaxArr2();
        System.out.println("\n-------------");
        findMaxArr3();
    }

    // 1.三层for循环求解
    // 2.二层for循环求解
    static void findMaxArr2()
    {
        int max = arr[0];// 最大值
        int sum;// 求和
        int startIndex = 0;
        int endIndex = 0;
        for (int i = 0; i <= maxIndex; i++)
        {
            sum = 0;
            for (int j = i; j <= maxIndex; j++)
            {
                sum += arr[j];
                if (sum > max)
                {
                    max = sum;
                    startIndex = i;
                    endIndex = j;
                }
            }
        }
        System.out.println("最大值为：" + max);
        printArr(startIndex, endIndex);
    }

    // 3.时间复杂度为n
    static void findMaxArr3()
    {
        int max = arr[0];// 最大值
        int sum = 0;// 求和
        int startIndex = 0;
        int endIndex = 0;
        for (int i = 0; i <= maxIndex; i++)
        {
            if (sum >= 0)
            {
                sum += arr[i];
            }
            else
            {
                sum = arr[i];
                startIndex = i;// 最大子数组开始值
            }
            if (sum > max)
            {
                max = sum;
                endIndex = i;// 最大子数组结束值
            }
        }
        System.out.println("最大值为：" + max);
        printArr(startIndex, endIndex);
    }

    // 根据下标开始结束值，打印数组
    static void printArr(int startIndex, int endIndex)
    {
        for (int i = startIndex; i <= endIndex; i++)
        {
            System.out.print(arr[i] + " ");
        }
    }

}

//源代码片段来自云代码http://yuncode.net