53. Maximum Subarray.md

53. Maximum Subarray

---

Difficulty : Easy

Related Topics : Array、Divide and Conquer、Dynamic Programming

---

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

• If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

---

Solution

• mine
  • Java
    • Runtime: 0 ms, faster than 100.00%, Memory Usage: 39.5 MB, less than 30.77% of Java online submissions

      // O(N)time
      // O(1)space
      public int maxSubArray(int[] nums) {
          int n = nums.length;
          if(n == 0) return 0;
          int pre = nums[0];
          int max = pre;
          for(int i = 1; i < n; i++){
              //if pre > 0, we plus it
              pre =  nums[i] + Math.max(pre, 0);
              max = Math.max(pre, max);
          }
          return max;
      }
      

---