【剑指offer-Java版】31连续子数组的最大和

左手的ㄟ右手 2022-08-21 09:48 112阅读 0赞

连续子数组最大和，要求O(n)时间复杂度

思路：核心思想就是当前遍历数组的时候，遇到的是一个正数，计算这个正数加上已有的和得到一个新的和  
如果这个新的和比当前的正数大，那么保留该和否者更新和为当前正数

书上173页的动态规划的公式也是适用于本例的

public class _Q31<T> {
        
    
        public int[] FindGreatestSumOfSubArray(int array[]){
            if(array == null) return null;
    
            int sum = 0, finalSum = Integer.MIN_VALUE;
            int startIndex = 0, finalStartIndex = 0;
            int endIndex = 0, finalEndIndex = 0;
    
            for(int i=0; i<array.length; i++){
                // // 无法处理数组都是负数的情况
        //          sum += array[i];
        //          
        //          // 当且仅当当前值大于零且其与之前的sum之和小于自身的时候，从新计算sum
        //          if(array[i] > 0 && sum < array[i]){
        
        //              startIndex = i;
        //              sum = array[i];
        //              endIndex = startIndex;
        //          }else{
        
        //              endIndex++;
        //          }
    
                // 可以解决所有类型用例
                if(sum <= 0){
                    sum = array[i];
                    startIndex = i;
                    endIndex = startIndex;
                }else{
                    sum += array[i];
                    endIndex++;
                }
    
                // 保留当前最大 -- 以避免else中由于不断的加负数，导致的和减少
                if(finalSum < sum){
                    finalStartIndex = startIndex;
                    finalEndIndex = endIndex;
                    finalSum = sum;
                }
            }
    
            System.out.println(finalSum);
    
            return Arrays.copyOfRange(array, finalStartIndex, finalEndIndex + 1);
        }
        }

测试代码：

public class _Q31Test extends TestCase {
        
    
        _Q31 subArraySum = new _Q31();
    
        public void test(){
            int nums1[] = {
       1, 1, 1, 1, 1, 1};
            int nums2[] = {
       1, -2, 3, 10, -4, 7, 2, -5};
            int nums3[] = {-5, -1, -2, -3, -4};
    
            subArraySum.FindGreatestSumOfSubArray(nums1);
            int result[] = subArraySum.FindGreatestSumOfSubArray(nums2);
            int result2[] = subArraySum.FindGreatestSumOfSubArray(nums3);
            CommonUtils.PrintArray(result);
            CommonUtils.PrintArray(result2);
        }
        }