Maximum Subarray Solutions in C++

// Source : https://oj.leetcode.com/problems/maximum-subarray/
// Author : Hao Chen
// Date   : 2014-06-20



#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define INT_MIN     (-2147483647 - 1)

int maxSubArray1(int A[], int n);
int maxSubArray2(int A[], int n); 

int max(int x, int y){
    return x>y?x:y;
}

int maxSubArray(int A[], int n) {
    if (random()%2){
        return maxSubArray1(A, n);
    }
    return maxSubArray2(A, n);
}

int maxSubArray1(int A[], int n) {
    int *sum = new int[n];
    sum[0] = A[0];
    int m = A[0]; 
    for (int i=1; i<n; i++){
        sum[i] = max(A[i], A[i] + sum[i-1]);
        m = max(m, sum[i]);
    }
    delete[] sum;
    return m;
}

int maxSubArray2(int A[], int n) {
    int m=INT_MIN;
    int sum=0;
    for (int i=0; i<n; i++){
        sum += A[i];
        m = max(sum, m);
        if (sum<0){
            sum = 0;
        }
    }
    return m;
}

int main()
{
    srand(time(NULL));
    int a[]= {-2,1,-3,4,-1,2,1,-5,4};
    printf("%d\n", maxSubArray(a, sizeof(a)/sizeof(int)));
    printf("%d\n", maxSubArray(a, sizeof(a)/sizeof(int)));
    return 0;
}

#include <algorithm>

class Solution {
public:
    int maxSubArray(int A[], int n) {
        int maxv = A[0];
        for (int i=0, benefited = 0; i != n; ++i)
        {
            benefited = std::max(A[i], benefited + A[i]);
            maxv = std::max(maxv, benefited);
        }
        return maxv;
    }
};

/// Source : https://leetcode.com/problems/maximum-subarray/
/// Author : liuyubobobo
/// Time   : 2020-04-03

#include <iostream>
#include <vector>

using namespace std;


/// Classical DP: Kadane's algorithm
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    int maxSubArray(vector<int>& nums) {

        int res = *max_element(nums.begin(), nums.end());
        if(res < 0) return res;

        int sum = 0;
        for(int e: nums){
            if(sum + e < 0) sum = 0;
            else{res = max(res, sum + e); sum += e;}
        }
        return res;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/maximum-subarray/
/// Author : liuyubobobo
/// Time   : 2020-04-03

#include <iostream>
#include <vector>

using namespace std;


/// Greedy
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    int maxSubArray(vector<int>& nums) {

        int res = nums[0], sum = nums[0];
        for(int i = 1; i < nums.size(); i ++){
            if(sum + nums[i] < nums[i]) sum = nums[i];
            else sum += nums[i];
            res = max(res, sum);
        }
        return res;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/maximum-subarray/
/// Author : liuyubobobo
/// Time   : 2020-04-03

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;


/// Divide and Conqure
/// Time Complexity: O(nlogn)
/// Space Complexity: O(logn)
class Solution {
public:
    int maxSubArray(vector<int>& nums) {

        assert(nums.size());
        return maxSubArray(nums, 0, nums.size() - 1);
    }

private:
    int maxSubArray(const vector<int>& nums, int l, int r){

        if(l == r) return nums[l];

        int mid = (l + r) / 2;
        int res = max(maxSubArray(nums, l, mid),
                      maxSubArray(nums, mid + 1, r));
        return max(res, crossSum(nums, l, mid, r));
    }

    int crossSum(const vector<int>& nums, int l, int mid, int r){

        int lres = nums[mid];
        int sum = lres;
        for(int i = mid - 1; i >= l; i --){
            sum += nums[i];
            lres = max(lres, sum);
        }

        int rres = nums[mid + 1];
        sum = rres;
        for(int i = mid + 2; i <= r; i ++){
            sum += nums[i];
            rres = max(rres, sum);
        }

        return lres + rres;
    }
};


int main() {

    vector<int> nums = {-2,1,-3,4,-1,2,1,-5,4};
    cout << Solution().maxSubArray(nums) << endl;
    // 6

    return 0;
}