题目
连续子数组求和
给定一个整数数组，请找出一个连续子数组，使得该子数组的和最大。输出答案时，请分别返回第一个数字和最后一个数字的值。（如果两个相同的答案，请返回其中任意一个）
样例
给定 [-3, 1, 3, -3, 4], 返回[1,4].
解题
法一：直接暴力，时间复杂度O(N2)，时间超时
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