JZ42 连续子数组的最大和

JZ42 连续子数组的最大和

连续子数组的最大和_牛客题霸_牛客网 (nowcoder.com)

---

// //贪心
// public class Solution {
//     public int FindGreatestSumOfSubArray(int[] array){
//         int sum=array[0];
//         int max=array[0];
//         for(int i=1;i<array.length;i++){
//             sum=Math.max(sum+array[i],array[i]);
//             if(sum>max){
//                 max=sum;
//             }
//         }
//         return max;
//     }
// }

//动规
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array){
        int[] dp=new int[array.length];
        dp[0]=array[0];
        int max=array[0];
        for(int i=1;i<array.length;i++){
            dp[i]=Math.max(dp[i-1]+array[i],array[i]);
            if(dp[i]>max){
                max=dp[i];
            }
        }
        return max;
    }
}