一、題目描述

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

成都創(chuàng)新互聯(lián)公司堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：做網(wǎng)站、成都網(wǎng)站設(shè)計(jì)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時(shí)代的雙柏網(wǎng)站設(shè)計(jì)、移動媒體設(shè)計(jì)的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！

二、解題思路

開始看到這道題是有點(diǎn)懵的，甚至想過用循環(huán)和數(shù)組去遍歷和記錄，自己的知識儲備的確還差得遠(yuǎn)！
后來，看到有個(gè)同學(xué)是用動態(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) {
        //動態(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