lintcode ：continuous subarray sum 连续子数组之和

题目

连续子数组求和

给定一个整数数组，请找出一个连续子数组，使得该子数组的和最大。输出答案时，请分别返回第一个数字和最后一个数字的值。（如果两个相同的答案，请返回其中任意一个）

样例

给定 [-3, 1, 3, -3, 4], 返回[1,4].

解题

法一：直接暴力，时间复杂度O(N²)，时间超时

public class Solution {

    /**

     * @param A an integer array

     * @return  A list of integers includes the index of the first number and the index of the last number

     */

    public ArrayList<Integer> continuousSubarraySum(int[] A) {

        // Write your code here

        ArrayList<Integer> result = new ArrayList<Integer>();

        int max = Integer.MIN_VALUE;

        for(int i = 0;i<A.length;i++){

            int sum = 0;

            for(int j = i;j<A.length; j++){

                sum += A[j];

                if(sum>max){

                    max = sum;

                    result.clear();

                    result.add(i);

                    result.add(j);

                }

            }

        }

        return result;

    }

}

Java Code

然后想到有过求最大子数组的和,只是返回最大子数组对于的和,本题是返回子数组的开始和结束的下标.

根据之前做题,突然想到,通过定义一个数组,来保存子数组的右边界是该元素时候的最大和,求出所有和的最大值就是最大子数组和的最大值.

public class Solution {

    /**

     * @param nums: A list of integers

     * @return: A integer indicate the sum of max subarray

     */

    public int maxSubArray(int[] nums) {

        // write your code

        int max = Integer.MIN_VALUE;

        int d[] = new int[nums.length];// 以i结束的元素的最大子数组之和

        d[0] = nums[0];

        max = d[0];

        for(int i=1 ;i<nums.length ; i++){

            d[i] = Math.max(d[i-1]+nums[i],nums[i]);

            max = Math.max(d[i],max);

            // System.out.println(d[i]);

        }

        return max;

    }

}

Java Code

可以看出,上面的数组其实可以换成两个变量的.之前看的网上的程序就是定义两个变量的.

本题是求的最大子数组的两个边界下标.

根据上面的思想,这个数组的下标是该子数组的右下标,而数组的值是子数组的左下标.。。。。然而发现实现不了。。。

网上就找到下面的程序，很好理解，但是自己写就会写乱。。。

public class Solution {

    /**

     * @param A an integer array

     * @return  A list of integers includes the index of the first number and the index of the last number

     */

    public ArrayList<Integer> continuousSubarraySum(int[] A) {

        // Write your code here

        ArrayList<Integer> result = new ArrayList<Integer>();

        int begin = 0;

        int end = 0;

        int sum = A[0];

        int maxsum = A[0];

        int maxbegin = 0;

        int maxend = 0;

        for(int i = 1;i<A.length;i++){

            if(sum <= 0){

                if(A[i] > sum){

                    begin = i;

                    end = i;

                    sum = A[i];

                }

                if(A[i] >= maxsum){

                    maxbegin = i;

                    maxend = i;

                    maxsum = A[i];

                }

            }else{

                sum +=A[i];

                if(sum> 0){

                    end = i;

                }

                if(sum > maxsum){

                    maxbegin = begin;

                    maxend = i;

                    maxsum = sum;

                }

            }

        }

        result.add(maxbegin);

        result.add(maxend);

        return result;

    }

}

Java Code

总耗时: 11178 ms

定义两对开始和结束的最大路径，一个用来保存当前路径的最大值得开始结束位置，一个用来保存所有路径的中最大值得开始结束位置。

当sum<0的时候并且A[i] > sum 更新begin End sum

　　当A[i] >=maxsum时候更新maxbegin maxend maxsum

当sum>0 sum+=A[i]

　　此时若sum > 0 end 更新为当前的 i

　　若 sum>maxsum 时候更新maxbegin maxend maxsum

最后结束的就是答案了

class Solution:

    # @param {int[]} A an integer array

    # @return {int[]}  A list of integers includes the index of the

    #                  first number and the index of the last number

    def continuousSubarraySum(self, A):

        # Write your code here

        begin,end,suma = 0,0,A[0]

        maxbegin,maxend,maxsum = 0,0,A[0]

        for i in range(1,len(A)):

            if suma < 0:

                if A[i] > suma :

                    begin = i

                    end = i;

                    suma = A[i]

                if A[i]>= maxsum:

                    maxbegin = i

                    maxend = i;

                    maxsum = A[i]

            else:

                suma +=A[i]

                if suma>0:

                    end = i

                if suma > maxsum:

                    maxbegin = begin

                    maxend = i

                    maxsum = suma

        return [maxbegin,maxend]

Python Code

总耗时: 673 ms

巴特西

lintcode ：continuous subarray sum 连续子数组之和

连续子数组求和

最新文章

热门文章