# Evolve from brute force to optimal, a review of all solutions

1. O(n^2), try all subarrays
``````    int maxSubArray(vector<int>& nums) {
int n=nums.size();
int ma=INT_MIN;
for(int i=0;i<n;i++) {
int s=0;
for(int j=i;j<n;j++) {
s+=nums[j];
ma = max(ma, s);
}
}
return ma;
}
``````
1. O(n), dp, for a subarray, we don't have to try both ends as above. We can just try one end. The next subarray sum can be computed from the previous one using the dp relation.
``````    int maxSubArray(vector<int>& nums) {
int pre =0, ma=INT_MIN;
for(int i=0;i<nums.size();i++) {
pre = pre>0? pre+nums[i]:nums[i];
ma= max(ma,pre);
}
return ma;
}
``````
1. O(nlogn) Naive divide and conquer. the max subarray is the max of the left, right, and the one that spans the boundary.
``````    int maxSubArray(vector<int>& nums) {
return maxSubArray(0,nums.size()-1,nums);
}
int maxSubArray(int l, int r, vector<int>& nums) {
if(l==r) return nums[l];
int mid= (l+r)/2;
int ms=maxSubArray(l,mid,nums);
ms=max(ms,maxSubArray(mid+1,r,nums));
int pre=0, ml=INT_MIN;
for(int i=mid;i>=l;i--) {
pre+=nums[i];
ml=max(ml,pre);
}
pre=0;
int mr=INT_MIN;
for(int i=mid+1;i<=r;i++) {
pre+=nums[i];
mr=max(mr,pre);
}
return max(ms,ml+mr);
}
``````
1. O(n) divide and conquer, the max subarray starting and ending at the boundary can be computed at the leaves and passed up. Idea is from @wyattliu
``````    int maxSubArray(vector<int>& nums) {
int ml, mr, sum;
return maxSubArray(0,nums.size()-1, ml, mr, sum, nums);
}
int maxSubArray(int l, int r, int& ml, int& mr, int& sum, vector<int>& nums) {
if(l==r) return ml = mr = sum = nums[l];
int mid= (l+r)/2, lml, lmr, lsum, rml, rmr, rsum;
int ms=maxSubArray(l,mid,lml,lmr,lsum,nums);
ms=max(ms,maxSubArray(mid+1,r,rml,rmr,rsum,nums));
ml = max(lml, lsum+rml);
mr = max(rmr, rsum+lmr);
sum = lsum+rsum;
return max(ms,lmr+rml);
}
``````

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