几个相关的题目
1.在数组中找出和最大的连续子串；
2.在数组中找出和最小的连续子串；
3.在循环数组中找出和最大的连续子串；
4.在数组中找出和最接近0的连续子串；
5.在数组中找出和最接近target值的连续子串；
1.在数组中找出和最大的连续子串
例如给定数组为A={1， 3， -2， 4， -5}， 则最大连续子序列和为6，即1+3+（-2）+ 4 = 6。
关键：当遍历到第i个元素时，判断在它前面的连续子序列和是否大于0，如果大于0，则以位置i结尾的最大连续子序列和为元素i和前门的连续子序列和相加；否则，则以位置i结尾的最大连续子序列和为元素i。
//最大子串和
public int maxSubSum(int arr[]){
int len = arr.length;
if(len == 0){
return 0;
}
int sum = arr[0];
int max = arr[0];
for(int i=1;i<len;i++){
if(sum > 0){
sum = sum + arr[i];
}else{
sum = arr[i];
}
if(max < sum){
max = sum;
}
}
return max;
}
2.在数组中找出和最小的连续子串
与1同理。
//最小子串和
public int minSubSum(int arr[]){
int len = arr.length;
if(len == 0){
return 0;
}
int sum = arr[0];
int min = arr[0];
for(int i=1;i<len;i++){
if(sum < 0){
sum = sum + arr[i];
}else{
sum = arr[i];
}
if(min > sum){
min = sum;
}
}
return min;
}
3.在循环数组中找出和最大的连续子串
把数组想象成一个首尾相连的环。
此题可分为两种情况：
①目标子串没有跨过最后一个节点，此时问题转化为题目1；
②目标子串跨过了最后一个节点，此时可以找到其对偶问题即最小和连续子串，去除最小子串后便是跨首尾的最大连续子串。
private int circleMaxSubSum(int[] a) {
int noCircleMax = maxSubSum(a);
int noCircleMin = minSubSum(a);
int totalSum = sum(a); //求和
int withCircleMax = totalSum - noCircleMin;
int circleMax = noCircleMax > withCircleMax ? noCircleMax : withCircleMax;
return circleMax;
}
4.在数组中找出和最接近0的连续子串
利用辅助数组sum[]，其中sum[i]表示arr[0],...,arr[i]之和。
想象一种情况，若恰好存在和为0的连续子串[i,....,j]，则sum[i-1]一定是等于sum[j].将问题转化为子串和数组中最接近的相邻两值。
则只需将sum数组快排后，两两比较求出最小差值即可。
//最接近目標0的字串和
//O(Nlog(N))
public int closestToZero(int arr[]){
int closest = Integer.MAX_VALUE;
int n = arr.length;
int sum[]= new int[n];
sum[0] = arr[0];
for(int i=1;i<n;i++){
sum[i] = sum[i-1]+arr[i];
}
Arrays.sort(sum); //快速排序
System.out.println(Arrays.toString(sum));
for(int i=sum.length-1;i>0;i--){
if(sum[i]-sum[i-1] < closest){
closest = sum[i]-sum[i-1];
}
}
return closest;
}
5.在数组中找出和最接近target值的连续子串
//最接近target的子串和
//沒有找到O(N)的方法，利用动态规划的思路O(N2)解決
public int closestToTarget(int arr[],int target){
int n = arr.length;
int sum = 0;
int closest = Integer.MAX_VALUE;
int delta,begin = -1,end = -1;
for(int i=0;i<n;i++){
sum = 0;
for(int j=i;j<n;j++){
sum = sum + arr[j];
delta = Math.abs(sum-target);
if(delta < closest){
closest = delta;
begin = i;
end = j;
}
}
}
return closest;
}