最大连续子数组

 1 public class MaxSubArray {
 2     
 3     public static int MaxArray(int [] arr,int n)
 4     {
 5         int maxSum = arr[0];
 6         int currSum;
 7         for(int i = 0;i<n;i++)
 8         {
 9             
10             for(int j = i ;j<n ;j++)
11             {
12                 currSum = 0;
13                 for(int k = i;k<j;k++)
14                 {
15                     currSum+=arr[k];
16                 }
17                 if(currSum>maxSum)
18                 {
19                     maxSum = currSum;
20                 }
21                 
22             }
23         }
24         
25         return maxSum;
26     }
27     public static void main(String[] args) {
28         
29         int [] array = {1,-2,3,10,-4,7,2,-5};
30         int maxArray = MaxArray(array, array.length);
31         System.out.println(maxArray);
32     }
33 
34 }

 1 //解法2.分治法求解
 2     public static int MaxAddSub(int [] arr,int from ,int to)
 3     {
 4         //定义递归的出口
 5         if(to == from )
 6             return arr[from];
 7         //求数组的中间位置
 8         int middle = (from + to)/2;
 9         //左边最大的子数组的和
10         int m1 = MaxAddSub(arr, from, middle);
11         //右边最大子数组的和
12         int m2 = MaxAddSub(arr,middle+1,to);
13         
14         //这种情况 就是最大的子序列在中间的情况
15         int i ,left = arr[middle],now = arr[middle];
16         for(i = middle -1;i>=from;--i)
17         {
18             now += arr[i];
19             //left中只保留向左 去的最大的自序列的情况
20             left = Math.max(now,left);
21         }
22         
23         
24         //向右的情况是从middle+1 开始的防止重复计算中间值的情况
25         int right = arr[middle+1];
26         now = arr[middle+1];
27         for( i = middle+2;i<= to;++i)
28         {
29             now += arr[i];
30             // right只保留向右最大的情况
31             right = Math.max(now,right);
32         }
33         //m3 是向左最大的情况加上向右的最大情况
34         int m3 = left+right; 
35         
36         //最中返回这个区间中三中情况中值最大的情况
37         return Math.max(Math.max(m1,m2),m3);
38         
39     }