关于算法-数据结构:算法最大子数组

40次阅读

共计 4505 个字符,预计需要花费 12 分钟才能阅读完成。

问题形容:

 给定一只股票在某段时间内的历史价格变动曲线,找出一个可能实现收益最大化的时间段。

了解:

 为找出最大化的收益,须要思考的是在买进和卖出时的价格变动幅度,因而从该股票的每日变动幅度来思考问题比拟适合。由此,能够将上述问题稍作变形:给定一只股票在某段时间内的每日变动幅度,找出一个适合的买进和卖出工夫,以实现收益最大化。因而,将输出数据转换如下,并试图在整个时间段中找到一个累加和最大的子区间,亦即最大子数组。

暴力求解:

 首先可能想到的是在一个给定数组(区间)中,其子数组(子区间)的个数是 C(2,n),很容易就能遍历完所有子数组从而找出最大的那个,其最坏状况渐进工夫复杂度是 Θ(n2)。假如每日变动幅度保留在数组 A 中(A 的下标从 1 到 n),A.length 示意 A 的元素个数,最终后果以元组模式返回;给出伪码如下:
BRUTE_FORCE(A)
            i = 1
            sum = -infinity
            for i <= A.length, inc by 1
                j = i
                last_sum = 0
                for j <= A.length, inc by 1
                    last_sum += A[j]
                    if last_sum > sum
                        sum = last_sum
                        start = i
                        end = j
            return (start, end, sum)

java 代码实现:

private static void bruteForce(int[] arr) {
  int start = -1, end = -1, max = 0;
  for (int i = 0; i < arr.length; i++) {
    // 定义 lastSum 的目标, 每一轮新的循环都须要从新累计
  int lastSum = 0;
  for (int j = i; j < arr.length; j++) {lastSum += arr[j];
    if (lastSum > max) {
      max = lastSum;
      start = i;
      end = j;
        }
    }
  }
  System.out.println("maxSum =" + max + ", start :" + start + ", end =" + end);
 }

分治求解:

 分治策略通常蕴含:合成子问题,解决子问题,合并子问题。由此能够推出大抵的解决思路:首先仍然假如数据输出如上一个办法那样,而后思考将 A[1...n] 拆分为规模大致相同的两个子数 left[1...mid] 和 right[mid+1...n],其中 mid=(1+n)/ 2 向下取整,那么能够必定,最大子数组要么在这两个子数组中,要么横跨这两个子数组,因而能够别离求解这三种状况,取其中最大的子数组并返回即可。对于 left/right 子数组可递归求解,而对于横跨两个子数组的状况,如果可能使得该状况下的求解工夫复杂度为 O(n),那么应该能让整体的最坏工夫复杂度低于 Θ(n2)。如果仅仅是通过遍历所有蕴含 A[mid] 和 A[mid+1] 的子数组来找最大子数组,那么很显然仅求解该状况就须要 Θ(n2) 的工夫。能够推断横跨两个子数组的最大子数组,必须由两个别离在 left/right 中的子数组组成,这两个子数组在别离蕴含了 A[mid] 和 A[mid+1] 的所有子数组中是最大的;因为如果存在一个不满足上述条件的最大子数组,那么总能够用上述办法找到一个更大的子数组。根据上述思路,很容易推知求解横跨两个子数组的状况只须要 O(n) 的工夫。由此给出伪码如下:(1)子过程:找出横跨两个子数组的最大子数组 
 FIND_CROSSING_MAX_SUBARRAY(A, low, mid, high)
                left_sum = -infinity
                sum = 0
                i = mid
                for i >= low, dec by 1
                    sum += A[i]
                    if sum > left_sum
                        left_sum = sum
                        left_index = i
                
                right_sum = -infinity
                sum = 0
                i = mid + 1
                for i <= high, inc by 1
                    sum += A[i]
                    if sum > right_sum
                        right_sum = sum
                        right_index = i
                return (left_index, right_index, left_sum+right_sum)
(2)主过程:分治法找出最大子数组 
FIND_MAX_SUBARRAY(A, low, high)
                if low == high
                    return (low, high, A[low])
                else
                    mid = down_trunc((low + high) / 2)
                    (left_start, left_end, left_sum) =
                        FIND_MAX_SUBARRAY(A, low, mid)
                    (right_start, right_end, right_sum) =
                        FIND_MAX_SUBARRAY(A, mid+1, high)
                    (cross_start, cross_end, cross_sum) =
                        FIND_CROSSING_MAX_SUBARRAY(A, low, mid, high)
                    
                    if left_sum > right_sum and left_sum > cross_sum
                        return (left_start, left_end, left_sum)
                    else if right_sum > left_sum and right_sum > cross_sum
                        return (right_start, right_end, right_sum)
                    else
                        return (cross_start, cross_end, cross_sum)

能够看出上述算法渐进工夫复杂度为 Θ(nlg(n))。
java 代码实现:

private static int[] findMaxSubArray(int[] arr, int left, int right) {
  // 合成到只有一个元素
 if (left == right) {return new int[]{left, right, arr[left]};
  }
  int mid = (left + right) / 2;
  int[] leftResult = findMaxSubArray(arr, left, mid);
  int[] rightResult = findMaxSubArray(arr, mid + 1, right);
  int[] crossingResult = findCrossingMaxSubArray(arr, mid, left, right);
  if (leftResult[2] > rightResult[2] && leftResult[2] > crossingResult[2]) {return leftResult;} else if (rightResult[2] > leftResult[2] && rightResult[2] > crossingResult[2]) {return rightResult;} else {return crossingResult;}
}

private static int[] findCrossingMaxSubArray(int[] arr, int mid, int left, int right) {
  int leftIndex = -1, rightIndex = -1, leftMax = Integer.MIN_VALUE, rightMax = Integer.MIN_VALUE, sum = 0;
  for (int i = mid; i >= left; i--) {sum += arr[i];
    if (sum > leftMax) {
      leftIndex = i;
      leftMax = sum;
    }
  }
  sum = 0;
  for (int i = mid + 1; i <= right; i++) {sum += arr[i];
    if (sum > rightMax) {
      rightIndex = i;
      rightMax = sum;
    }
  }
  return new int[]{leftIndex, rightIndex, leftMax + rightMax};
}

缩减问题规模:

缩减问题规模的办法:

 在查找过程中,是否能够依据现有的信息,来缩减须要排查的子数组个数,进而取得更好的工夫复杂度呢?一个思路是不再反复查看以前累加过的元素,即从左至右累加元素,保留其中的最大子数组,如果在退出一个元素后累加和为正数,则从该元素的后一个元素从新累加,直至整个数组遍历结束。该思路无效的前提是证实以下几个假如:1.  能够将最大子数组起源分为三种:曾经遍历完的数组局部、未遍历的数组局部以及逾越这两局部的子数组
2.  能够假如当从左至右累加直至累加和为负,所得的最大子数组是以后已遍历完的数组局部中最大的
3.  能够假如当累加和为负时,潜在的最大子数组不可能从该元素或该元素右边的元素开始

假如 1 不证自明。假如从 A[1] 累加到 A[i] 时第一次遇到其累加和为负(1<=i<=n),那么 A[i] 肯定为负,且 A[1]+...+A[i-1]>=0。当 i <= 2 时,显然此时假如 2 成立。当 i >2 时,能够认为在 A[1]...A[i] 中,所有子数组可分为三种:从 A[1] 开始向右拓展、从 A[i] 开始向左拓展以及不蕴含 A[1] 和 A[i] 的两头子数组;显然从 A[i] 向左拓展的不可能是最大子数组,而如果不蕴含 A[1] 和 A[i] 的两头子数组是最大子数组,那么能够使该两头子数组加上其右边的局部形成一个新的子数组,而且该子数组总是大于等于这个两头子数组,因为其右边局部总是大于等于 0,所以该状况下假如 2 也得证。综合来看假如 2 是成立的。对于假如 3,显然潜在的最大子数组不可能从 A[i] 开始,因为 A[i]<0。当潜在的最大子数组从 A[i] 的右边开始时,假如其从 A[j] 开始(1<=j<i)。显然 j 不能等于 1,因为 A[1]+...+A[i]<0;当 j >1 时,A[j]+...+A[i] 肯定是正数,因为 A[1]+...+A[j-1] 肯定大于等于 0 而 A[1]+...+A[i] 肯定为负。所以综合来看,从 A[i] 或者 A[i] 的右边寻找潜在的子数组是没有意义的。伪码如下,工夫复杂度为 Θ(n)。对于全副是正数的状况,非凡解决即可,不影响工夫复杂度。
 LINEAR_SEARCH_MAX_SUBARRAY(A)
            sum = -infinity
            start = 0
            end = 0

            cur_sum = 0
            cur_start_index = 1

            i = 1
            for i <= A.length, inc by 1
                cur_sum += A[i]
                if cur_sum < 0
                    cur_sum = 0
                    cur_start_index = i + 1
                else
                    if sum < cur_sum
                        sum = cur_sum
                        start = cur_start_index
                        end = i

            return (start, end, sum)

java 代码如下:

private static int[] linerSearchMaxSubArray(int[] nums) {
  int start = 0;
  int end = 0;
  int max = 0;
  int temp = 0;
  int ts = 0;
  for (int i = 0; i < nums.length; i++) {temp += nums[i];
    if (temp < 0) {
      ts = i + 1;
      temp = 0;
    } else {if (temp > max) {
        start = ts;
        end = i;
        max = temp;
      }
    }
  }
  return new int[]{start, end, max};
}

参考文章:https://www.cnblogs.com/SyBlog/p/11371922.html#commentform
参考书籍:《算法导论》

正文完
 0