最大连续子列和问题(Java)

矫情吗；* 2021-12-24 17:33 213阅读 0赞

1 public class test
     2 {
     3     public static void main(String[] args)
     4     {
     5         int[] array = new int[] {13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
     6         int max_sum = Integer.MIN_VALUE;
     7         
     8         //method1: Brutal Force O(N^2)
     9         for(int i = 0; i < array.length; i++)
    10         {
    11             int sum = 0;
    12             for(int j = i; j < array.length; j++)
    13             {
    14                 sum += array[j];
    15                 if(sum > max_sum)
    16                     max_sum = sum;
    17             }
    18         }
    19         System.out.println("The maximum sum is: " + max_sum);
    20         
    21         //method2: Divide and Conquer O(NlogN)
    22         max_sum = Maximum_Subarray(array, 0, array.length - 1);
    23         System.out.println("The maximum sum is: " + max_sum);
    24         
    25         //method3: 在线处理 O(N)
    26         int cur_sum = 0;
    27         for(int i = 0; i < array.length; i++)
    28         {
    29             cur_sum += array[i];
    30             if(cur_sum > max_sum)
    31                 max_sum = cur_sum;
    32             else if(cur_sum < 0)
    33                 cur_sum = 0;
    34         }
    35         System.out.println("The maximum sum is: " + max_sum);
    36 
    37         //method4: DP(Dynamic Programming) O(N)
    38         int[] dp = new int[array.length];
    39         int tmpMax = array[0];
    40         dp[0] = array[0];
    41         for(int i = 1; i < dp.length; i++)
    42         {
    43             tmpMax += array[i];
    44             dp[i] = max(dp[i - 1], tmpMax);
    45             if(tmpMax < 0)
    46                 tmpMax = 0;
    47         }
    48         System.out.println("The maximum sum is: " + dp[dp.length - 1]);
    49     }    
    50     
    51     public static int Maximum_Subarray(int[] array, int left, int right)
    52     {
    53         if(left == right)
    54             return array[left];
    55         
    56         int mid = left + (right - left) / 2;
    57         int left_max = Maximum_Subarray(array, left, mid);  //左子列的最大子列和
    58         int right_max = Maximum_Subarray(array, mid + 1, right);  //右子列的最大子列和
    59         int crossing_max = Maximum_Crossing_Subarray(array, left, right, mid);
    60         return max(left_max, right_max, crossing_max);
    61     }
    62     
    63     public static int Maximum_Crossing_Subarray(int[] array, int left, int right, int mid)
    64     {
    65         int l_sum = 0, l_max = Integer.MIN_VALUE;
    66         for(int i = mid; i >= left; i--)
    67         {
    68             l_sum += array[i];
    69             if(l_sum > l_max)
    70                 l_max = l_sum;
    71         }
    72         int r_sum = 0, r_max = Integer.MIN_VALUE;
    73         for(int i = mid + 1; i <= right; i++)
    74         {
    75             r_sum += array[i];
    76             if(r_sum > r_max)
    77                 r_max = r_sum;
    78         }
    79         return l_max + r_max;
    80     }
    81 }

转载于:https://www.cnblogs.com/Huayra/p/10923849.html