连续子数组和最大有关问题

  1 //连续子数组和最大问题
  2 //test case
  3 //[31,-41,59,26,-53,58,97,-93,-23,84]
  4 //59+26+(-53)+58+97=187和最大
  5 
  6 public class Solution {
  7     private static int a[] = new int[] {-1,-2,-3};
  8 
  9     public static void main(String[] args) {
 10         // long startTime = System.currentTimeMillis();
 11         int res = method5(a);
 12         // long endTime = System.currentTimeMillis();
 13         // System.out.println("执行时间为：" + (endTime - startTime) + "ms");
 14         System.out.println(res);
 15 
 16     }
 17 
 18     /**
 19      * 穷举法 三层循环，时间复杂度为O(n^3)
 20      */
 21     public static int method1(int[] a) {
 22         int sum;
 23         int max = Integer.MIN_VALUE;
 24         int n = a.length;
 25         for (int i = 0; i < n; i++) {
 26             for (int j = i; j < n; j++) {
 27                 sum = 0;
 28                 for (int k = i; k <= j; k++) {
 29                     sum += a[k];
 30                 }
 31                 /* sum is sum of a[i...j] */
 32                 max = Math.max(max, sum);
 33             }
 34         }
 35         return max;
 36     }
 37 
 38     /**
 39      * 对穷举法的改进1 时间复杂度为O(n^2)
 40      */
 41     public static int method2(int[] a) {
 42         int n = a.length;
 43         int sum;
 44         // cumarr为累加数组，如cumarr[5]记录了数组前6项之和
 45         int cumarr[] = new int[n];
 46         cumarr[0] = a[0];
 47         for (int i = 1; i < n; i++) {
 48             cumarr[i] = cumarr[i - 1] + a[i];
 49         }
 50 
 51         int max = Integer.MIN_VALUE;
 52         // a[i...j]之和 = cumarr[j]-cumarr[i-1]
 53         for (int i = 0; i < n; i++) {
 54             for (int j = i; j < n; j++) {
 55                 sum = 0;
 56                 if (i == 0) {
 57                     sum = cumarr[j];
 58                 } else {
 59                     sum = cumarr[j] - cumarr[i - 1];
 60                 }
 61                 max = Math.max(max, sum);
 62             }
 63 
 64         }
 65         return max;
 66     }
 67 
 68     /**
 69      * 对穷举法的改进2
 70      * 时间复杂度为O(n^2)
 71      */
 72     public static int method3(int[] a) {
 73         int max = Integer.MIN_VALUE;
 74         int sum;
 75         int l = a.length;
 76         for (int i = 0; i < l; i++) {
 77             sum = 0;
 78             for (int j = i; j < l; j++) {
 79                 sum += a[j];
 80                 if (sum > max) {
 81                     max = sum;
 82                 }
 83             }
 84         }
 85         return max;
 86     }
 87 
 88 
 89     public static boolean isAllNegative(int[] a) {
 90         for (int i = 0; i < a.length; i++) {
 91             if (a[i] > 0) {
 92                 return false;
 93             }
 94         }
 95         return true;
 96     }
 97 
 98     /**
 99      * 貌似这个是Kadane算法？
100      * 算法依据： 假如数组元素全为正数，那么最大值必然为全部数相加
101      * 假如数组中有负数，如果加上某个负数，子数组和小于0，那么最大和的子数组必然不包括这个负数
102      * 时间复杂度为O(n)
103      */
104     public static int method4(int[] a) {
105         // 数组元素全部为负数的情况
106         if (isAllNegative(a)) {
107             return a[0];
108         }
109         int max = 0, temp = 0;
110         for (int i = 0; i < a.length; i++) {
111             temp += a[i];
112             if (temp < 0) {
113                 temp = 0;
114             } else {
115                 if (temp > max) {
116                     max = temp;
117                 }
118             }
119         }
120         return max;
121     }
122     
123     /**
124      * 动态规划的后无效性
125      * 时间复杂度为O(n)
126      */
127     public static int method5(int [] array){
128         int n=array.length;  
129         int all=array[n-1],start=array[n-1];  
130         int count=0;  
131         for(int i=n-2;i>=0;i--){  
132             if((start+array[i])>array[i]){  
133                 start=start+array[i];  
134             }else{  
135                 start=array[i];  
136             }  
137             if(all<start){  
138                 all=start;  
139             }  
140             count++;  
141         }  
142         System.out.println("数组长度="+array.length+"||时间复杂度="+count);    
143         return all;  
144     }
145 }