首页 > 其他 > 详细

Leetcode 53 Maximum SubArray

时间:2015-07-14 07:31:33      阅读:229      评论:0      收藏:0      [点我收藏+]

---恢复内容开始---

方法1:brute force 

  时间复杂度 O(n^2)  空间复杂度 O(1)

public class Solution {
  public int maxSubArray(int[] nums) {
    if (nums == null || nums.length == 0) {
      return 0;
    }

    int ans = Integer.MIN_VALUE;
    for (int start_index = 0; start_index < nums.length; start_index++) { // starting index
      int sum = 0;
      for (int sub_size = 1; start_index + sub_size - 1 < nums.length; sub_size++) { // subarray size
        sum += nums[i + j - 1];
        max = Math.max(max, sum);
      }
    }
    return ans;
  }
}

 

方法2:Divide and Conquer

  时间复杂度  空间复杂度

 

public class Solution {
  public int maxSubArray(int[] nums) {
    if (nums == null || nums.length == 0) {
      return 0;
    }
    return helper(nums, 0, nums.length - 1);
  }

  private int helper(int[] nums, int start, int end) {
    if (start == end) {
      return nums[start];
    }
    int mid = start + (end - start) / 2;
    int left_MSS = helper(nums, start, mid);
    int right_MSS = helper(nums, mid + 1, end);
    int leftsum = Integer.MIN_VALUE;
    int rightsum = Integer.MIN_VALUE;
    int sum = 0;
    for (int i = mid + 1; i <= end; i++) {
      sum += nums[i];
      rightsum = Math.max(rightsum, sum);
    }
    sum = 0;
    for (int j = mid; j >= 0; j--) {
      sum += nums[j];
      leftsum = Math.max(leftsum, sum);
    }
    int ans = Math.max(left_MSS, right_MSS);
    return Math.max(ans, leftsum + rightsum);
  }
}

    

---恢复内容结束---

Leetcode 53 Maximum SubArray

原文:http://www.cnblogs.com/janedr/p/4644427.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!