Go语言视频零基础入门到精通

javalearner

给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n],求该序列如a+a[i+1]+…+a[j]的子段和的最大值。
当所给的整数均为负数时定义子段和为0，依此定义，所求的最大值为：

Max{0,a+a[i+1]+…+a[j]},1<=i<=j<=n
例如，当（a1,a2,a3,a4,a4,a6）=(-2,11,-4,13,-5,-2)时，最大子段和为20.

1. import java.util.Scanner;
   
2. public class MaxSequence{
   
3. 
   
4.    public static   int[] findMaxSequence(int n, int[] seq){
   
5.     /* seq为传入的整型数组，n为数组长度， start, end分别用来返回所找到的最长子串的起始下标和截止下标 */
   
6.           int maxsofar = 0;
   
7.           int maxendinghere = 0;
   
8.           int starthere = 0;
   
9.           int start=0;
   
10.           int end= 0;
    
11.           for ( int i = 0; i < n; i++ )
    
12.           {
    
13.                if ( maxendinghere + seq[i] >= 0 )
    
14.                     maxendinghere = maxendinghere + seq[i];
    
15.                else
    
16.                {
    
17.                    maxendinghere = 0;
    
18.                    starthere = i+1;
    
19.                }
    
20.                if ( maxendinghere > maxsofar ||((maxendinghere == maxsofar) && (end - start) < (i - starthere)))
    
21.                {
    
22.                   maxsofar = maxendinghere;
    
23.                   start = starthere;
    
24.                   end = i;
    
25.                }
    
26.            }
    
27.            return new int[]{start,end,maxsofar};
    
28.       }
    
29.      
    
30. public static void main(String[] args) {
    
31.   /**
    
32.    *从键盘输入所要求的序列的长度n
    
33.    */
    
34.   Scanner in=new Scanner(System.in);
    
35.   int n=in.nextInt();
    
36.   
    
37.   /**
    
38.    *从键盘输入所要求的数组，存储在a[n]中
    
39.    */
    
40.   int[] a=new int[n];
    
41.   for(int i=0;i< n;i++) {
    
42.    a[i]=in.nextInt();
    
43.   }
    
44.    int result[]=findMaxSequence(n,a);
    
45.    System.out.println("最大子段和是:"+result[2]);
    
46.    System.out.println("最大子段和构成:");
    
47.    for(int i=result[0];i<=result[1];i++)
    
48.       System.out.print(a[i]+"  ");
    
49.   }
    
50. }
    
51.   
    
52. C:        est>java   MaxSequence
    
53. 15
    
54. 1 2 -1 1 3 2 -2 3 -1 5 -7 3 2 -2 -1
    
55. 最大子段和是:13
    
56. 最大子段和构成:
    
57. 1  2  -1  1  3  2  -2  3  -1  5
    
58. C:        est>java   MaxSequence
    
59. 6
    
60. -2 11 -4 13 -5 -2
    
61. 最大子段和是:20
    
62. 最大子段和构成:
    
63. 11  -4  13
    

复制代码

  


源码下载：http://file.javaxxz.com/2014/12/6/000710343.zip