Lintcode题目 Continuous Subarray Sum II 有几个test过不了

http://www.lintcode.com/en/problem/continuous-subarray-sum-ii/#

在可以循环的数组里面找最大的subarray sum，最开始想的是复制一份数组，然后跟之前的subarray sum一样做，但是有test过不了。然后改进算法，two pass记录第一次的位置然后搜索到当前的index的前一个index，但是这样时间复杂度太高了。看这题AC率才9%，有没有人成功通过的？求共享算法或者代码交流

最大数组的范围只有两种可能：1. [ i ~ j ]，2. [ i ~ N-1] + [ 0 ~ j ]. 所以，你只要分别找到两种情况的最大者，取这两个最大者中较大的即可。1和Continuous Subarray Sum I相同，就不多说了。2等价于找一个范围[j+1 ~i-1]，使得这个范围内的数组和最小。这又等价于将原数组取负号，然后在这个负数组中找最大和的[j+1 ~ i+1]范围即可。

和楼上的想法是一样的，代码如下。感觉逻辑和内存使用上都有优化的空间，目前属于逼近TLE的水平。。楼主随便参考一下就好

1. public ArrayList<Integer> continuousSubarraySumII(int[] A) {
   
2.         // Write your code here
   
3.         if(A.length==0)
   
4.             return new ArrayList<Integer>();
   
5.         int max=Integer.MIN_VALUE;
   
6.         int min=Integer.MAX_VALUE;
   
7.         ArrayList<Integer> maxIndex=new ArrayList<Integer>();
   
8.         ArrayList<Integer> minIndex=new ArrayList<Integer>();
   
9.         for(int i=0;i<2;i++){
   
10.             maxIndex.add(0);
    
11.             minIndex.add(0);
    
12.         }
    
13.         int[] maxArr=new int[A.length];
    
14.         int[] minArr=new int[A.length];
    
15.         int[] maxStart=new int[A.length];
    
16.         int[] minStart=new int[A.length];
    
17.         maxArr[0]=A[0];
    
18.         minArr[0]=A[0];
    
19.         int sum=A[0];
    
20.         for(int i=1;i<A.length;i++){
    
21.             sum+=A[i];
    
22.             if(maxArr[i-1]>0){
    
23.                 maxArr[i]=maxArr[i-1]+A[i];
    
24.                 maxStart[i]=maxStart[i-1];
    
25.             }
    
26.             else{
    
27.                 maxArr[i]=A[i];
    
28.                 maxStart[i]=i;
    
29.             }
    
30.             if(minArr[i-1]<0){
    
31.                 minArr[i]=minArr[i-1]+A[i];
    
32.                 minStart[i]=minStart[i-1];
    
33.             }
    
34.             else{
    
35.                 minArr[i]=A[i];
    
36.                 minStart[i]=i;
    
37.             }
    
38.             if(maxArr[i]>max){
    
39.                 max=maxArr[i];
    
40.                 maxIndex.set(0,maxStart[i]);
    
41.                 maxIndex.set(1,i);
    
42.             }
    
43.             if(minArr[i]<min){
    
44.                 min=minArr[i];
    
45.                 minIndex.set(0,(i+1)%A.length);
    
46.                 minIndex.set(1,minStart[i]-1>=0?minStart[i]-1:A.length-1);
    
47.             }
    
48.         }
    
49.         if(max>sum-min||min==sum)
    
50.             return maxIndex;
    
51.         else
    
52.             return minIndex;
    
53.     }

复制代码

stellari 发表于 2015-7-6 09:27
最大数组的范围只有两种可能：1. [ i ~ j ]，2. [ i ~ N-1] + [ 0 ~ j ]. 所以，你只要分别找到两种情况的 ...

我后来想的改进方法就是这样的  可是时间复杂度太高了  在lintcold上超过1wms了 觉得可以有更好的方法

glaciersilent 发表于 2015-7-6 10:25
和楼上的想法是一样的，代码如下。感觉逻辑和内存使用上都有优化的空间，目前属于逼近TLE的水平。。楼主随 ...

我也是这个想法  还没想到更好的 lintcode上跑时间太久了

stevenlordiam 发表于 2015-7-6 10:32
我也是这个想法  还没想到更好的 lintcode上跑时间太久了

one pass O(n)算法已经是理论上最优了，当然我觉得可以靠多判断或者摆弄array之类的少用内存少存取来提高速度 我感觉lintcode的时间随便看看就好。。很简单的题和很复杂的题都可以到1w以上 又没有百分比 不像LC的有参考价值。。这题的阈值我觉得可能是2W，目前这个算法最好可以有1w2左右

stevenlordiam 发表于 2015-7-6 10:31
我后来想的改进方法就是这样的  可是时间复杂度太高了  在lintcold上超过1wms了 觉得可以有更好的方法

时间复杂度和实际执行时间没有必然联系啊。这个算法的时间复杂度是O(N)，不可能比这个时间复杂度再优了。实际执行时间过长可能是因为后台的测试用例太大的缘故。

glaciersilent 发表于 2015-7-6 10:45
one pass O(n)算法已经是理论上最优了，当然我觉得可以靠多判断或者摆弄array之类的少用内存少存取来提高 ...

运行时间长是因为java真的很慢，常系数太大。。复杂度没有问题的，不论是one pass还是two pass
换成C++写一遍的话，时间会短很多的。有些OJ上用C++的vector、cin都超时，必须改成数组、scanf。复杂度的常系数差别有时很惊人。

stellari 发表于 2015-7-6 11:02
时间复杂度和实际执行时间没有必然联系啊。这个算法的时间复杂度是O(N)，不可能比这个时间复杂度再优了。 ...

对 我开始想错了 我的做法类似的two pass 应该是2N = N

stevenlordiam 发表于 2015-7-6 10:31
我后来想的改进方法就是这样的  可是时间复杂度太高了  在lintcold上超过1wms了 觉得可以有更好的方法

这个题可以分两步啊， 第一步和Continuous Subarray Sum相同，第二步相当于求 -A 的Continuous Subarray Sum， 然后看看第一步的结果和 数组总和减掉第二步的结果 哪个大，就知道是否是循环数组了。 我用C++的结果是1Kms左右