Leetcode --- Maximum Subarray(Easy)
===

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

A subarray is a contiguous part of an array.

### Examples

* Ex1
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
* Ex2:
Input: nums = [5,4,-1,7,8]
Output: 23

### Constraints

* 1 <= nums.length <= 3 * 10^4^
* -10^5^ <= nums[i] <= 10^5^

## Solution

* **Brute Force:**
I can list all of probably subarrays,for example:
take the a as head : a , ab , abc ......
take the b as head : b , bc .....
....
Easliy,I am maintaining the maximum vaule throughout all of subarrays,then the ultimate maximum is gonna be my goal.

* **Complexity analysis**
* **Time Complexity**
The number of all of probably subarrays are n+(n-1)+...+1 => **O(n^2^)**
and the longest subarray will be added n-1 times => **O(n)**
==Overall time complexity :==
O(n^2^)*O(n) = **O(n^3^)**
* **Space Complexity**
all of probably subarrays will be saved in size n+(n-1)+...+1 => **O(n^2^)**

* **Accelerating Brure Froce**
memorize: sum[i] = sum[i-1] + A[i]
for instance:
a : a , (a)+b , (a+b)+c .....
b : b , (b)+c , (b+c)+d.....
.....
Therefore,the each subarray sum can be calculated in linear time if known the previous subarray,the longest subarray is gonna become O(1).
* **Complexity analysis**
O(n^2^)*O(1) = **O(n^2^)**
* **Space Complexity**
**O(n^2^)**

---

* ==**kadane algorithm**==

It is a DP solution.
Typically,if we want to consrtcut a DP equation,we have two ideas for defination of subproblem:
* The subproblem is the same as the original problem
For example : the original problem is maximum subarray of length n,and the subproblem is also maximum subarray but size would be smaller than original length like n-1.
* The subproblem is not the same as the original problem

* The idea One:
First,I would like to test the idea one and the test data is [-2,1,-3,4,-1,2,1,-5,4]:
dp[0] = -2
dp[1] = 1
dp[2] = 1
dp[3] = 4
dp[4] = 4
dp[5] = 5
dp[6] = 6
dp[7] = 6
dp[8] = 6
Obviously,these answers could not easily find the neat equation.
Therefore,I have to use the idea two to try to find the answer.

* The idea Two:
==TRICK:== A~i~ denotes the answer to the subproblem from index 0 to index i
Note : In other words,the answer to the subproblem must include the data of index i.

I only need to compare A~0~,A~1~....,A~n-1~ to find which has the maximum answer as the answer to the original problem.

=> What's the connection between A~i~ and A~i-1~?
There are four situations respect to answer about A~i-1~ and A[i]:
1. A~i-1~ >0 && A[i] >0 => A~i~ = A~i-1~ +A[i]
2. A~i-1~ >0 && A[i] <0 => A~i~ = A~i-1~ +A[i]
3. A~i-1~ <0 && A[i] >0 => A~i~ = A[i]
4. A~i-1~ <0 && A[i] <0 => A~i~ = (A~i-1~ +A[i]) > A[i] ? A~i-1~ +A[i] : A[i]

Concluding all of situations,the DP eqation will be like ...


* Currently the complexity analysis:
* Time Complexity:
Find all of the answer to subproblem would be cost O(n)
Compare all of the answer to subpoblem would be cost O(n)
Overall time complexity : O(n) + O(n) =**O(n)**
* Space Complexity:
Store all of the answer to subproblem would be cost **O(n)**

Kadane algorithm :
We can use the pointer to maintian the maxumum vaule instead of saving all of answer to subproblem,therefore,**space complexity will down toO(1)**.

## Implement code

class Solution {
    public int maxSubArray(int[] nums) {
        
        if(nums.length ==1)
            return nums[0];
        int ans=nums[0];
        for(int i =1,cur=nums[0];i<nums.length;i++)
        {
            cur = cur +nums[i] > nums[i] ? cur+nums[i] : nums[i];
           // cur = Math.max(cur+nums[i],nums[i]);
            ans = ans>cur ? ans : cur;
        }
        return ans ;
    }
}

## Reference
https://zhuanlan.zhihu.com/p/85188269

###### tags: `Leetcode` `DP` `Easy` `Algorithm`