1. int [] arr = {4, -3, 5, -2, -1, 2, 6, -2};

复制代码

求它最大子序列的和，即它的子序列中和为最大的那个序列的和。

是不是大于零的数相加就是它的最大子序列。这样的话就很简单了。

木华 发表于 2014-6-22 23:04
是不是大于零的数相加就是它的最大子序列。这样的话就很简单了。

序列是有序的队列。子序列就是指比如{4,-3,5}，而{4,5}不是。

完全看不懂是什么意思

class A
{
        public static void main(String[] args)
        {
       
                int [] arr = {4, -3, 5, -2, -1, 2, 6, -2};;
                System.out.println(max_sub(arr,arr.length));
        }
        public static int max_sub(int a[],int size)
        {
                 int i,j,v,max=a[0];
                 for(i=0;i<size;i++)
                 {
                          v=0;
                          for(j=i;j<size;j++)
                          {
                                   v=v+a[j];
                                   if(v>max)
                                                max=v;
                          }
                 }
                 return max;
        }
}
穷举所有子序列   最大子序列和是11

1. public class Demo {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 int[] arr = { 4, -3, 5, -2, -1, 2, 6, -2 };
   
5.                
   
6.                 //定义一个变量接受最后的最大值
   
7.                 int big = arr[0];
   
8.                 //定义为数组中任意一个元素,如果定义0,在数组都为负数情况下会计算错误
   
9.                
   
10.                 //外围for循环取得某一子序列的开始位置,内层for循环取得任意子序列的结尾位置
    
11.                 for (int i = 0; i < arr.length; i++) {
    
12.                         for (int j = i; j < arr.length; j++) {
    
13.                                 if (sum(arr, i, j) > big) {//如果某个子序列和大于big,将该值赋给big
    
14.                                         big = sum(arr, i, j);
    
15.                                 }
    
16.                         }
    
17.                 }
    
18. 
    
19.                 System.out.println(big);//打印输出最后的big值
    
20.         }
    
21. 
    
22.        
    
23.         //定义一个函数,计算出给出数组中从i角标开始到角标结束之间元素的和
    
24.         public static int sum(int[] arr, int i, int j) {
    
25.                 int sum = 0;
    
26.                 for (int k = i; k <= j; k++) {
    
27.                         sum += arr[k];
    
28.                 }
    
29.                 return sum;//返回计算的结果
    
30.         }
    
31. }

复制代码