题解 | #连续子数组的最大和#
连续子数组的最大和
http://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484
动规
dp[i]表示第i个位置的最大和
判断前一个位置的最大和dp[i-1]是正是负
正数:dp[i]=dp[i-1]+array[i]
负数dp[i]=array[i];
同时用一个变量max记录最大值
public int FindGreatestSumOfSubArray(int[] array) { 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]; max=max>dp[i]?max:dp[i]; } else{ dp[i]=array[i]; max=max>dp[i]?max:dp[i]; } } return max; }