4.1最大子数组问题

在这里提出的题目类似如下：
121. 买卖股票的最佳时机
给定一个数组prices，它的第 i个元素 prices[i]表示一支给定股票第i天的价格。
你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回0。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 104

基本简单解答如下：

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         int min = Integer.MAX_VALUE;
  4.         int max = 0;
  5.         for (int i=0;i<prices.length;i++) {
  6.             if (prices[i] < min) {
  7.                 min = prices[i];
  8.             }else if (prices[i] - min > max){
  9.                 max = prices[i] - min;
  10.             }
  11.         }
  12.         return max;
  13.     }
  14. }

或者这题：
53. 最大子序和
给定一个整数数组nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [0]
输出：0
示例 4：
输入：nums = [-1]
输出：-1
示例 5：
输入：nums = [-100000]
输出：-100000

提示：

  • 1 <= nums.length <= 3 * 104

  • -105<= nums[i] <= 105

    1. class Solution {
    2.   public int maxSubArray(int[] nums) {
    3.       int ans = nums[0];
    4.       int max = nums[0];
    5.       for (int i=1;i<nums.length;i++){
    6.           max = Math.max(nums[i],max+nums[i]);
    7.           ans = Math.max(max,ans);
    8.       } 
    9.       return ans;
    10.   }
    11. }

    使用书本中的分治策略代码实现如下：

    1. class Solution {
    2.   public int maxSubArray(int[] nums) {
    3.       int len = nums.length;
    4.       int[] ans = findMaxNum(nums,0,len-1);
    5.       return ans[2];
    6.   }
    8.   public int[] findMaxCrossingSubArray(int[] nums,int low,int mid,int high) {
    9.       int leftSum = Integer.MIN_VALUE;
    10.       int sum = 0;
    11.       int maxLeft = 0;
    12.       for (int i=mid;i>=low;i--) {
    13.           sum += nums[i];
    14.           if (sum > leftSum) {
    15.               leftSum = sum;
    16.               maxLeft = i;
    17.           }
    18.       }
    19.       sum = 0;
    20.       int maxRight = 0;
    21.       int rightSum = Integer.MIN_VALUE;
    22.       for(int i=mid+1;i<=high;i++) {
    23.           sum += nums[i];
    24.           if (sum>rightSum) {
    25.               rightSum = sum;
    26.               maxRight = i;
    27.           }
    28.       }
    29.       return new int[]{maxLeft,maxRight,leftSum+rightSum}; 
    30.   }
    32.   public int[] findMaxNum(int[] nums,int low,int high) {
    33.       if (low == high) return new int[]{low,high,nums[low]};
    34.       else {
    35.           int mid = low + (high-low)/2;
    36.           int[] left = findMaxNum(nums,low,mid);
    37.           int[] right = findMaxNum(nums,mid+1,high);
    38.           int[] cross = findMaxCrossingSubArray(nums,low,mid,high);
    39.           if (left[2] >= right[2] && left[2] >= cross[2]) {
    40.               // return new int[]{left[0],left[1],left[2]};
    41.               return left;
    42.           }else if (right[2] >= left[2] && right[2] >= cross[2]) {
    43.               // return new int[]{right[0],right[1],right[2]};
    44.               return right;
    45.           }else {
    46.               return cross;
    47.           }
    48.       }
    49.   }
    50. }