题解 | 连续子数组的最大和

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型
     */
  //思路：
  //dp【i】：以i结尾的最大子数组和
  //因为要求子数组连续，所以dp[i]只能从dp[i-1]转换而来。
  //如果dp[i-1]>0，则加到dp[i]，如果dp[i-1]<=0,则不加到dp[i],因为会使dp[i]更小
  //最长子数组可能在中间，所以维护一个变量存储最长值
    public int FindGreatestSumOfSubArray (int[] array) {
        // write code here
        int n=array.length;
        int[] dp=new int[n+1]; //以i结尾的最大子数组和
        dp[1]=array[0];
        int ans=dp[1];
        for(int i=2;i<=n;i++){
            if(dp[i-1]>0){
                dp[i]=dp[i-1]+array[i-1]; 
            }else{
                 dp[i]=array[i-1];
            }
            if(dp[i]>ans){
                ans=dp[i];
            }
        }

        return ans;
    }
}