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

//本题用动态规划求解

//本题第一种第二种方法思路大致相似，具体实现不同
//dp【i】和temp一个含义，是以第i个元素结尾的最大子数组的和
//转移方程为 ：dp[i - 1] > 0 ? dp[i] = dp[i-1] + array[i] : dp[i] = array[i];
//(表达式格式不对，但是意思就是这个意思，勿喷）

public class Solution {

    public int FindGreatestSumOfSubArray (int[] array) {
        //参考大佬更简洁代码
        //temp记录中间计算值
        int temp = 0;
	    //ans记录最大值，充当了记忆化作用
        int ans = Integer.MIN_VALUE;
		
	  	//本题关键思路，：temp记录的是以第i个元素结尾的子数组的和，当前面的temp大于0时，直接加上最新的array【i】值，反之，最大值为他本身；
        for (int i = 0; i < array.length; i++) {
            if (temp > 0) {
                temp += array[i];
            } else {
                temp = array[i];
            }
			//ans记录最大的temp值
            if (temp > ans) {
                ans = temp;
            }
        }
        return ans;
        /*   int[] dp  = new int[array.length];

           dp[0] = array[0];
           int max = dp[0];


           for (int i = 1; i < array.length; i++) {
               if (dp[i-1] >0){
                   dp[i] = dp[i-1] + array[i];
               }else {
                   dp[i] = array[i];
               }
               if (dp[i] > max){
                   max = dp[i];
               }
           }

           return max;*/
    }
}