https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484?tpId=13&tqId=11183&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

題目：{6,-3,-2,7,-15,1,2,2},連續(xù)子向量的最大和為8(從第0個(gè)開始,到第3個(gè)為止)

image.png

圖片來源：https://www.nowcoder.com/questionTerminal/459bd355da1549fa8a49e350bf3df484

問題拆解：

1. 給定一個(gè)數(shù)組A，求任意位置i的連續(xù)子數(shù)組最大和 （[ A[0], A[i] ]）:
   Res(A[i]) = max(Res(A[i-1])+A[i], A[i]) :
   A[i]的連續(xù)子數(shù)組最大和 == max(A[i]的連續(xù)子數(shù)組最大和+A[i], A[i] )

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int locMax = array[0];
        int gloMax = array[0];
        
        for(int i=1; i<array.length; i++) {  // 注意，初始從1開始（因?yàn)?已經(jīng)被賦為初值了）
            locMax = Math.max(locMax+array[i], array[i]);
            gloMax = Math.max(gloMax, locMax);
        }
        
        return gloMax;
    }
}

如果要輸出連續(xù)子數(shù)組最大和，以及對(duì)應(yīng)的最大數(shù)組長度：

public int[] maxSubArraySum(int[] arr) {
        int globalMax = arr[0], localMax = arr[0], glbSta = 0, glbEnd = 0, locSta = 0;

        for (int i = 1; i < arr.length; i++) {
            if (localMax < 0) {  // 丟棄之前的累加和（負(fù)的只沒用）；只有這個(gè)時(shí)候最大連續(xù)子數(shù)組起點(diǎn)會(huì)變
                localMax = 0;
                locSta = i;
            }

            localMax += arr[i];

            if (globalMax < localMax) {
                globalMax = localMax;
                glbSta = locSta;
                glbEnd = i;
            }

            if(globalMax == localMax && glbEnd - glbSta < i - locSta) {
                glbSta = locSta;
                glbEnd = i;
            }

        }

        return new int[]{globalMax, glbSta, glbEnd};
    }