连续子数组最大和，可考虑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public  class  Solution {
     public  int  maxSubArray( int [] nums) {
         int  len=nums.length;
         if (nums== null  || len== 0 ) return  0 ;
         int  MAX=nums[ 0 ];
         int  curSum=nums[ 0 ];
         for ( int  i= 1 ;i<len;i++){
             if (curSum> 0 ){
                 curSum+=nums[i];
             } else {
                 curSum=nums[i];
             }
             MAX=Math.max(curSum,MAX);
         }
         return  MAX;
     }
}

连续子数组绝对值最大，可考虑

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
//求子数组的和的绝对值的最大值
//先计算所有sum[0-j] 0<= j < n ，然后对sum[0-j]的数组进行排序，那么对于任何i,j段的和等于：sum[i-j]= sum[0-j] - sum[0-i];
//设置数组sum用来存储子数组0-j的和
//因为已经对sum进行了排序，排序后只需要找到sum[sum.size()-1]-sum[0],sum[z]  (0<=z<sum.size())的绝对值的最大值即可。z为排序后的索引
//如果是sum[z]情形，z为排序后的索引，则maxAbs = abs(sum[0-i])
//如果是sum[sum.size()-1]-sum[0]情形，则maxAbs = abs(sum[i]-sum[j])
//时间复杂度：o(nlogn) 空间复杂度：o(n)
public int maxAbsSum2(int[] num)
{
     if(num.length()==0) return 0;
     if(num.length()==1) return Math.abs(num[0]);
     int max_abs_sum;
     int[] sum = new int[num.length()];
     int cur_sum = 0;
     for(int  i = 0 ; i<num.length(); i++)
     {
         cur_sum += num[i];
         if(cur_sum == 0)
             return 0;
         sum[i] = cur_sum;
     }
     Arrays.sort(sum);
     max_abs_sum = Math.abs(sum[sum.length()-1]-sum[0]);
     for(int  i = 0 ; i<sum.length(); i++)
     {
         cur_sum = Math.abs(sum[i]);
         if(cur_sum>max_abs_sum)
             max_abs_sum = cur_sum;
     }
     return max_abs_sum;
}