# Solution by DasongLi

• #### Approach #1 Brute Force [Time Limit Exceeded]

Intuition

Check all the contiguous subarray one by one to find the maxinum.

Algorithm

In first loop, `i` represents the position where one subarray begins. And in second loop, `j` represents the postion where this subarray ends. In this way, we can check all the subarrays.

c++

``````class Solution {
public:
int maxSubArray(vector<int>& nums) {
int i,j,k,l; i = 0;
int max1=INT_MIN, max2=INT_MIN;
for (i=0;i<nums.size();i++) {
int sum = 0;
for (j=i;j<nums.size();j++) {
sum = sum+nums[j];
if (sum>max2) max2 = sum;
}
}
return max2;
}
}
``````

Complexity Analysis

• Time complexity : )\$\$O(n^2)\$\$.
This program uses two loops to check all the subarrays. so the time complexity is \$\$O(n^2)\$\$.

• Space complexity : \$\$O(1)\$\$.
. This program stores the biggest data in array. so the space complexity is \$\$O(1)\$\$.

#### Approach #2 Dividing and Conquering [Accepted]

Intuition

We need to use another method to decrease time. First I think out this method --- Dividing and Conquering

Algorithm

for mid position of one subarray whose range is `[begin, end]` , I consider the following three conditions.

• 1.the left subarray whose range is `[begin, mid]` (Suppose the target subarray is on the left part)
• 2.the right subarray whose range is `[mid, end]` (Suppose the target subarray is on the right part)
• 3.the best result contains mid. I traverse the array by two directions. find the best result.

I compare these three conditions and choose the biggest result.

Another Point
if all the elements' values are less than or equal 0, I select the biggest value as the final result.

c++

``````class Solution {
private:
int maxm(int a, int b, int c) {
return max(max(a,b),c);
}
int search(vector<int>& nums,int begin,int end) {
if (begin>end) return 0;
if (begin == end) return max(nums[begin],0);
if (end-begin==1) return maxm(nums[begin],nums[end],nums[begin]+nums[end]);
int mid = (begin+end)/2,sum1=0,sum2=0,max1=0,max2=0;
for (int i=mid+1;i<=end;i++) {
sum1 = sum1 + nums[i];
if (sum1>max1) max1 = sum1;
}
for (int i=mid-1;i>=begin;i--) {
sum2 = sum2 + nums[i];
if (sum2>max2) max2 = sum2;
}

return maxm(search(nums,begin,mid),search(nums,mid,end),nums[mid]+max2+max1);
}
public:
int maxSubArray(vector<int>& nums) {
int i,j,k,l; i = 0;
int max1=INT_MIN, max2=INT_MIN;
for (i=0;i<nums.size();i++) {
if (nums[i]>max2) max2 = nums[i];
}
if (max2<=0) return max2;
return search(nums,0,nums.size()-1);
}
}
``````

Complexity Analysis

• Time complexity : \$\$O(n*log n)\$\$.
This program use recursive method to achieve Dividing and Conquering. At one recursive time, the time complexity for checking the third condition is \$\$O(n)\$\$.

• Space complexity : \$\$O(1)\$\$.
. the space complexity is \$\$O(1)\$\$.

#### Approach #3 Dynamic Programming [Accepted]

Intuition

The \$\$O(n*log n)\$\$ is also big, we need to optimize the program. The key is Dynamic Programming.

Algorithm
The state transition formula is `sum[i] = max(sum[i-1]+a[i],a[i])`. `sum[i]` means the sum which accumulates values from some place and ends at `i`. After one loop, I get the biggest result for subarray which ends at `i`.

Note
Similar to Approach #2, if all the elements' values are less than or equal 0, I select the biggest value as the final result.
c++

``````class Solution {
public:
int maxSubArray(vector<int>& nums) {
int i,j,k,l; i = 0;
int max1=INT_MIN, max2=INT_MIN;
for (i=0;i<nums.size();i++) {
if (nums[i]>max2) max2 = nums[i];
}
if (max2<=0) return max2;
vector<int> res(nums.size(),0);
if (nums.size()==1) return nums[0];
for (i=0;i<nums.size();i++) {
if (nums[i]>max2) max2 = nums[i];
}
if (max2<=0) return max2;
res[0] = max1 = max(nums[0],0);
for (i=1;i<nums.size();i++) {
if (res[i-1]+nums[i]>nums[i]) {
res[i] = res[i-1]+nums[i];
} else {
res[i] = nums[i];
}
}
for (i=1;i<nums.size();i++) {
if (res[i]>max1) max1 = res[i];
}
return max1;
}
}
``````

Complexity Analysis

• Time complexity : \$\$O(n)\$\$. We just use loop to get the best results. So the time complexity is \$\$O(n)\$\$.

• Space complexity : \$\$O(1)\$\$.
the space complexity is \$\$O(n)\$\$.

#### Approach #4 Optimized Dynamic Programming [Accepted]

Algorithm
I don't use one array to store the results. I just use one variable to store the best result for all subarrays which start from anywhere and end at `i` .

Note
From my perspective, this code is easy to understand.

c++

``````class Solution {
public:
int maxSubArray(vector<int>& nums) {
int i,j,k,l; i = 0;
int max1=INT_MIN, max2=INT_MIN,sum=0;
while (i<nums.size()) {
sum = sum + nums[i];
if (sum>max1) max1 = sum;
if (sum < 0 and i<nums.size()-1) sum = 0;
i++;
}
return max1;
}
}
``````

Complexity Analysis

• Time complexity : \$\$O(n)\$\$. We just use one while-loop to get the best results. So the time complexity is \$\$O(n)\$\$.

• Space complexity : \$\$O(1)\$\$.
the space complexity is \$\$O(n)\$\$.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.