Description: Given an array of integers, find a contiguous subarray which has the largest sum.
Example: Given the array [−2,2,−3,4,−1,2,1,−5,3], the contiguous subarray [4,−1,2,1] has the largest sum = 6.
Challenge: Can you do it in time complexity O(n)?

My direct , idiotic，and complex solution. 100% test AC. All Rights Reserved.

Considering neighbored numbers with same sgn.

    int maxSubArray(vector<int> &nums) {
        // write your code here
        int maxval=nums[0];
        int sum2=0, i=0, len = nums.size();
        vector<int> record;
        int ind_beg = 0;
        while (ind_beg<len && nums[ind_beg] < 0) {
            if (nums[ind_beg]>maxval) 
                maxval = nums[ind_beg];
            ind_beg++;
        } 
        if (ind_beg == len)
            return maxval; // if there is no positive number in the array
        sum2 += nums[ind_beg];
        maxval = nums[ind_beg];
        for (i = ind_beg+1; i < len; i++) {
            if (nums[i]>maxval)  maxval = nums[i];
            if (nums[i] < 0) {
                int judge1 = nums[i++];
                while (i<len && nums[i] < 0) judge1 += nums[i++];
                if (i == len) {
                    record.push_back(sum2);
                    break;
                }
                int judge2 = nums[i++];
                while (i<len && nums[i]>=0) judge2 += nums[i++];
                if (judge1+sum2<=0) {
                    record.push_back(sum2);
                    sum2 = judge2;
                }
                else {
                    if (judge1 + judge2 >= 0) 
                        sum2 += judge1 + judge2;
                    else {
                        record.push_back(sum2);
                        sum2 += judge1 + judge2;
                    }
    
                }
                if (i == len) {
                    record.push_back(sum2);
                    break;
                }
                i--;
            }
            else 
                sum2 += nums[i];
        }
        record.push_back(sum2);
        record.push_back(maxval);  // if there is only one positive value
        int sub_seq = record.size();
        int best = record[0];
        for (i = 1; i<sub_seq; i++) {
            if (record[i]>best)
                best = record[i];
        }
        return best;
    }