1. import org.junit.jupiter.api.Test;
    3. public class SumMaximumContinuity {
    5.     int[] arr = {1,2,3,-6,1};
    7.     /**
    8.      * 暴力
    9.      * @param arr
    10.      * @return
    11.      */
    12.     public int getMaxSum(int[] arr){
    13.         int n = arr.length;
    14.         int max_sum = arr[0];
    15.         for (int i = 0; i < n; i++) {
    16.             int cur_sum = 0;
    17.             for (int j = i; j < n; j++) {
    18.                 cur_sum += arr[j];
    19.                 if (cur_sum>max_sum){
    20.                     max_sum = cur_sum;
    21.                 }
    22.             }
    23.         }
    24.         return max_sum;
    25.     }
    27.     /**
    28.      * 动态规划
    29.      * @param arr
    30.      * @return
    31.      */
    32.     public int getMaxSumDynamic(int[] arr){
    33.         int n = arr.length;
    34.         int max_sum = arr[0];
    35.         int cur_sum = 0;
    36.         for (int i = 0; i < n; i++) {
    37.             cur_sum += arr[i];
    38.             if (cur_sum > max_sum){
    39.                 max_sum = cur_sum;
    40.             }
    41.             if (cur_sum < 0){
    42.                 cur_sum = 0;
    43.             }
    44.         }
    45.         return max_sum;
    46.     }
    48.     /**
    49.      * 分治法
    50.      * @param arr
    51.      * @return
    52.      */
    53.     public int getMaxSumDivide(int[] arr){
    54.         int n = arr.length;
    55.         return getMaxSumDivide(arr,0,n-1);
    56.     }
    58.     /**
    59.      * 分治法
    60.      * @param arr
    61.      * @param left
    62.      * @param right
    63.      * @return
    64.      */
    65.     public int getMaxSumDivide(int[] arr,int left,int right){
    66.         int sum;
    67.         //只有一个元素
    68.         if (left == right){
    69.             return arr[left];
    70.         }
    71.         int mid = (left+right)/2;
    72.         int leftSum = getMaxSumDivide(arr,left,mid);
    73.         int rightSum = getMaxSumDivide(arr,mid+1,right);
    75.         //左半部分
    76.         int s_left = 0;
    77.         int lefts = 0;
    78.         for (int i = mid; i >= left; i--) {
    79.             lefts += arr[i];
    80.             if (lefts>s_left)
    81.                 s_left = lefts;
    82.         }
    84.         //右半部分
    85.         int s_right = 0;
    86.         int rights = 0;
    87.         for (int i = mid+1; i <= right; i++) {
    88.             rights += arr[i];
    89.             if (rights>s_right)
    90.                 s_right = rights;
    91.         }
    93.         //求三者最大值
    94.         sum = s_left + s_right;
    95.         if (sum<leftSum)
    96.             sum = leftSum;
    97.         if (sum<rightSum)
    98.             sum = rightSum;
    100.         return sum;
    101.     }
    104.     @Test
    105.     public void demo01(){
    106.         int maxSum = getMaxSum(arr);
    107.         System.out.println(maxSum);
    108.     }
    110.     @Test
    111.     public void demo02(){
    112.         int maxSum = getMaxSumDynamic(arr);
    113.         System.out.println(maxSum);
    114.     }
    116.     @Test
    117.     public void demo03(){
    118.         int maxSum = getMaxSumDivide(arr);
    119.         System.out.println(maxSum);
    120.     }
    121. }