劍指Offer3_連續(xù)子數(shù)組的最大和

一、題目描述

HZ偶爾會(huì)拿些專業(yè)問題來忽悠那些非計(jì)算機(jī)專業(yè)的同學(xué)。今天測(cè)試組開完會(huì)后,他又發(fā)話了:在古老的一維模式識(shí)別中,常常需要計(jì)算連續(xù)子向量的最大和,當(dāng)向量全為正數(shù)的時(shí)候,問題很好解決。但是,如果向量中包含負(fù)數(shù),是否應(yīng)該包含某個(gè)負(fù)數(shù),并期望旁邊的正數(shù)會(huì)彌補(bǔ)它呢？例如:{6,-3,-2,7,-15,1,2,2},連續(xù)子向量的最大和為8(從第0個(gè)開始,到第3個(gè)為止)。給一個(gè)數(shù)組，返回它的最大連續(xù)子序列的和，你會(huì)不會(huì)被他忽悠??？(子向量的長度至少是1)

二、解題思路

開始看到這道題是有點(diǎn)懵的，甚至想過用循環(huán)和數(shù)組去遍歷和記錄，自己的知識(shí)儲(chǔ)備的確還差得遠(yuǎn)！
后來，看到有個(gè)同學(xué)是用動(dòng)態(tài)規(guī)劃做的，原諒我當(dāng)時(shí)還不清楚這個(gè)。但大佬講的很清楚，我也基本理解了一點(diǎn)。直接截的那位同學(xué)的題解：
?？玩溄樱?br/>https://www.nowcoder.com/questionTerminal/459bd355da1549fa8a49e350bf3df484?f=discussion

三、代碼

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        //動(dòng)態(tài)規(guī)劃
        int maxArr=array[0];//包含當(dāng)前元素array[i]在內(nèi)的一個(gè)連續(xù)子,數(shù)組的最大值
        int maxVal=array[0];//記錄所有子數(shù)組中的最大值
        for(int i=1;i<array.length;i++){
            maxArr=Math.max(maxArr+array[i],array[i]);//可以確定連續(xù)子數(shù)組的起始位置
            maxVal=Math.max(maxVal,maxArr);
        }
        return maxVal;
    }