NC19 连续子数组的最大和（暴力法+动态规划）

ゞ浴缸里的玫瑰 2022-09-16 15:20 161阅读 0赞

## 暴力法 ##

public class Solution {
        
        public int FindGreatestSumOfSubArray(int[] array) {
        
            int len=array.length;
            int max=Integer.MIN_VALUE;  //先给max一个最小的数
            for(int i=0;i<len;i++){
             //i标记起始位置
                for(int j=i;j<len;j++){
         //j标记末尾位置
                    int tmp=0;
                    for(int k=i;k<=j;k++){
         // 遍历i到j，求和（注意是k<=j）
                        tmp=tmp+array[k];  // 从i到j求和              
                    }
                    max=Math.max(tmp,max);  // 保留从i到j最大的值
                }
            }
            return max; // 结束循环时返回的就是子数组的最大和
        }
    }

## 动态规划 ##

dp\[i\]表示以array\[i\]为结尾的所有子数组的最大和。先从dp\[0\]=array\[0\]开始往后遍历  
如果dp\[i-1\]是正数，那么加上array\[i\]就得到了更大的数，因此dp\[i\]=dp\[i-1\]+array\[i\]  
如果dp\[i-1\]是负数，那么再加上array\[i\]只会让dp\[i\]变小，所以此时的dp\[i\]就是array\[i\]，表示不要前面的数了，就从i开始  
遍历完一遍就可以得到连续子数组的最大和

public class Solution {
        
        public int FindGreatestSumOfSubArray(int[] array) {
        
            int len=array.length;
            int[] dp=new int[len]; // 以i为结尾的所有子数组的最大和
            dp[0]=array[0];
            int max=dp[0];
            for(int i=1;i<len;i++){
        
                dp[i]=Math.max(array[i],dp[i-1]+array[i]); // 要么只取自己，要么加上前一个的dp值
                max=Math.max(max,dp[i]);      // 保留最大值      
            }
            return max;
        }
    }