最大子段和问题的四种算法（暴力法、优化后的暴力法、分治算法、动态规划算法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
import java.util.Random;
import java.util.Scanner;

public class maxSum {
  public static void main(String[] args){

    Scanner scan = new Scanner(System.in);
    Random rd = new Random();

    System.out.println("请输入数据规模n（10的倍数）：");
    int n = scan.nextInt();
    int[] a = new int[n];
    for(int i=0; i<n; i++){
    a[i] = rd.nextInt(20)-10;  
  }//初始化数组，生成-10~10的随机数
  
  /*
  * test暴力法
  */
  long startMili1 = System.currentTimeMillis();
  maxSum ms1 = new maxSum();
  System.out.println("最大子序列和：" + ms1.maxSum(a));
  long endMili1 = System.currentTimeMillis();
  System.out.println("暴力法总耗时："+ (endMili1 - startMili1));
  
  /*
  * test优化后的暴力法
  */
  long startMili2 = System.currentTimeMillis();
  maxSum ms2 = new maxSum();
  System.out.println("最大子序列和：" + ms2.maxSumBF(a));
  long endMili2 = System.currentTimeMillis();
  System.out.println("总耗时："+ (endMili2 - startMili2));
   
  /*
  * test分治算法
  */
  long startMili3 = System.currentTimeMillis();
  maxSum ms3 = new maxSum();
  System.out.println("最大子序列和：" + ms3.maxSumFZ(a));
  long endMili3 = System.currentTimeMillis();
  System.out.println("总耗时："+ (endMili3 - startMili3));

  /*
  * test动态规划算法
  */
  long startMili4 = System.currentTimeMillis();
  maxSum ms4 = new maxSum();
  System.out.println("最大子序列和：" + ms4.MaxSumDynamic(a));
  long endMili4 = System.currentTimeMillis();
  System.out.println("总耗时："+ (endMili3 - startMili3));

  }

  //暴力法(O(n^3))
  public static int maxSum(int a[]){
  int n = a.length - 1;
  int sum = 0;
  for(int i=1; i<=n; i++){
    for(int j=1; j<=n; j++){
      int thissum = 0;
      for(int k=i; k<=j; k++){
        thissum += a[k];
      }
      if(thissum>sum){
        sum = thissum;
      }
    }
  }
  return sum;
}

//优化后的暴力法 (O(n^2))
public int maxSumBF(int a[]){
  int n = a.length - 1;
  int sum = 0;
  for(int i=1; i<=n; i++){
    int thissum = 0;
    for(int j=i; j<=n; j++){
      thissum += a[j];
      if(thissum>sum){
        sum = thissum;
      }
    }
  }
  return sum;
}

  //分治算法(n log(n))
  private static int maxSubSum(int a[], int left, int right){
  int sum = 0;
  if(left == right){
     sum = a[left]>0?a[left]:0;
  }else{
    int center = (left + right)/2;
    int leftsum = maxSubSum(a,left,center);
    int rightsum = maxSubSum(a,center+1,right);
    int s1 = 0;
    int lefts = 0;
    for(int i=center; i>=left; i--){
      lefts += a[i];
      if(lefts>s1){
      s1 = lefts;
    }
  }
  int s2 = 0;
  int rights = 0;
  for(int i=center+1; i<=right; i++){
    rights += a[i];
    if(rights>s2){
      s2 = rights;
    }
  }
    sum = s1 + s2;
    f(sum<leftsum){
      sum = leftsum;
    }
    if(sum<rightsum){
      sum = rightsum;
    }
  }
  return sum;
}

public static int maxSumFZ(int a[]){
  return maxSubSum(a,1,a.length-1);
}

//动态规划算法(O(n))
public static int MaxSumDynamic(int a[]){
  int n = a.length-1;
  int sum = 0,b = 0;
  for(int i=1; i<=n; i++){
    if(b>0){
      b += a[i];
    }else{
    b = a[i];
  }
  if(b>sum){
    sum = b;
  }
 }
return sum;
}
}