L1-最大子数组,最小子数组

Posted on | In | 27

最大子数组

暴力求解法 时间复杂度O（n^3）

暴力枚举，时间复杂度O（n3）
1、找出子数组的最左端点 for i<- 1 to n

2、找出子数组的最右端点 for j<- i to n

3、求和，找出最大值

sum = nums[i] +……+nums[j]; ans = max(ans, sum)

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
public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
	public int maxSubArray(int[] nums)
	{
		int n=nums.length;
		int max=nums[0],sum;
		for(int i=0;i<n;i++)//找出子数组的最左端点
		{
			for(int j=i;j<n;j++)//找出子数组的最右端点
			{
			sum=0;
				for(int k=i;k<=j;k++)
				{
					sum+=nums[k];
					if(sum>=max)
					max=sum;
					
					
				}	
			}	
		}
		return max;
	}

}

image
时间复杂度O（n3） 求和操作被执行了很多次，有很多是重复计算的。

优化枚举 时间复杂度O（n^2）

算是半个暴力吧

原理：左端点相同的子数组，随着长度的增加，排在前面的元素被不断重复相加。如果我们记录下之前的求和结果，

就不需要对前面的元素再进行计算，比上面的少了一重循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int maxSubArray(int[] nums)
	{
		if(nums==null||nums.length==0) 
			 throw new IllegalArgumentException("array is null or empty.");
		int n=nums.length;
		int ans=Integer.MIN_VALUE;
		for(int i=0;i<n;i++)//找出子数组的最左端点
		{
			int sum=0;
			for(int j=i;j<n;j++)//找出子数组的最右端点
			{
				sum+=nums[j];
				if(sum>ans)
				ans=sum;
				
			}	
		}
		return ans;
	}

动态规划 时间复杂度O（n）

【只有子数组“前半部分”的和为正数时，子数组的求和才有可能最大】，在这个trick条件下，只需要遍历一次数组就可以。算法是：当从头开始遍历的元素的求和为正数时，继续向后遍历。当求和为负数时，重新开始计算求和，子数组的开始重置为下一个元素。

即对于任意一个子数组和，如果大于0，那么它再添加一个数，他的贡献是正值，如果子数组和小于0，再添加一个数，它的贡献则为负值，这时候不如将当前子数组舍掉，新数成为一个新数组。

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
package a;

public class Solution {
	/**
	 * @param matrix
	 *            : matrix, a list of lists of integers
	 * @param target
	 *            : An integer
	 * @return: a boolean, indicate whether matrix contains target
	 */
	public static int maxSubArray(int[] nums)
	{
		if(nums==null||nums.length==0) 
			 throw new IllegalArgumentException("array is null or empty.");
		int n=nums.length;
		int max=Integer.MIN_VALUE;
		int sum=0;
		for(int i=0;i<n;i++)//找出子数组的最左端点
		{
	    sum=sum<0?nums[i]:sum+nums[i];
		if(sum>max)
			max=sum;
	    
		}
       return max;
	}
    public static void main(String[] args) {
        int maxSum = maxSubArray(new int[]{-100, -3, -10, -1, -7, -2, -5});
        System.out.println(maxSum);
    }
}

其实虽然原题中指出数组里有正数和负数，经过实践和思考，这个算法同样适用于全是正数，或者全是负数的情况。当全为正数时，最大的和自然就是所有元素的和，当全为负数时，最大和自然就是其中最大的那个负数的值。通过此算法都能得到相应的结果。

最小子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    /*
     * @param nums: a list of integers
     * @return: A integer indicate the sum of minimum subarray
     */
    public int minSubArray(List<Integer> nums) {
        // write your code here
     	
		if(nums==null||nums.size()==0) 
			 throw new IllegalArgumentException("array is null or empty.");
		int n=nums.size();
		int min=nums.get(0);
		int sum=0;
		for(int i=0;i<n;i++)//找出子数组的最左端点
		{
	    sum=sum>0?nums.get(i):sum+nums.get(i);
		if(sum<min)
			min=sum;
	    
		}
		return min;
	}   
}

可参考
https://blog.csdn.net/wwe4023/article/details/72953559
http://www.cnblogs.com/theskulls/p/4886531.html