中国大学MOOC-陈越、何钦铭-数据结构-2020春——最大子列和问题Java实现代码

求最大子列和问题实现代码1、2、4
Java实现
 1 import java.util.Scanner;
 2 
 3 public class main{
 4     public static void main(String[] args) {
 5         Scanner scanner = new Scanner(System.in);
 6         int N=0;
 7         N = scanner.nextInt()+1;
 8        // N=N+1;
 9         int []arr=new int[N];
10 
11         int i=0;
12         for(;i<N;i++){
13             arr[i]=i;
14         }
15         long startTime1 = System.nanoTime();//开始计时
16         int Max1=MaxSubseqSum1(arr,N);
17         long estimatedTime1 = System.nanoTime()-startTime1;//
18         System.out.println((Max1+"  "+estimatedTime1+"纳秒"));
19 
20         long startTime2 = System.nanoTime();//开始计时
21         int Max2=MaxSubseqSum2(arr,N);
22         long estimatedTime2 = System.nanoTime()-startTime2;//
23         System.out.println((Max2+"  "+estimatedTime2+"纳秒"));
24         
25         long startTime4 = System.nanoTime();//开始计时
26         int Max4=MaxSubseqSum4(arr,N);
27         long estimatedTime4 = System.nanoTime()-startTime4;//结束计时，求的总时长
28         System.out.println(Max4+"  "+estimatedTime4+"纳秒");
29         
30     }
31 
32     private static int MaxSubseqSum1(int[] arr, int n) {
33         int MaxSum=0,ThisSum;
34         int i,j,k;
35         for (i = 0;i < n;i++) {/* i是子列左端位置 */
36             for (j = i; j < n; j++) {/* j是子列右端位置 */
37                 ThisSum = 0;/* ThisSum是从A[i]到A[j]的子列和 */
38                 for (k = i;k <= j;k++){
39                     ThisSum =arr[k]+ThisSum;
40                     if (ThisSum > MaxSum){/* 如果刚得到的这个子列和更大 */
41                         MaxSum = ThisSum; /* 则更新结果 */
42                     }
43                 }
44             }/* j循环结束 */
45         }/* i循环结束 */
46         return MaxSum;
47     }
48 
49     private static int MaxSubseqSum2(int[] arr, int n) {
50         int ThisSum,MaxSum=0;
51         int i=0,j;
52         for (;i<n;i++){/* i是子列左端位置 */
53             ThisSum = 0;/* ThisSum是从A[i]到A[j]的子列和 */
54             for(j = i;j < n;j++){/* j是子列右端位置 */
55                 ThisSum = arr[j]+ThisSum;/*对于相同的i，不同的j，只要在j-1次循环的基础上累加1项即可*/
56                 if(ThisSum>MaxSum)/* 如果刚得到的这个子列和更大 */
57                     MaxSum = ThisSum;   /* 则更新结果 */
58             } /* j循环结束 */
59         }/* i循环结束 */
60         return MaxSum;
61     }
62 
63 
64 
65     private static int MaxSubseqSum4(int[] arr, int n) {
66         int ThisSum,MaxSum;
67         ThisSum=MaxSum=0;
68         int i = 0;
69         for(;i<n;i++){
70             ThisSum = arr[i]+ThisSum;/*向右累加*/
71             if(ThisSum >= MaxSum)/*发现更大和则更新当前结果*/
72                 MaxSum = ThisSum;/*如果当前子列和为负*/
73             else
74                 ThisSum=0;/*则不可能使后面的部分和增大，抛弃之*/
75 
76         }
77         return MaxSum;
78     }
79 
80 }