I think the problem is wrong. It should be "containing at least one positive number" in the description.


  • 0
    Y

    or the accepted algorithm cant handle all negative numbers situation


  • 0
    S

    What's your accepted algorithm? Could you please update your post to share it?

    My solution is ok with all negative numbers, do not have to do any special check. Main idea is accumulate the sum of a[i], if sum < 0, then refresh sum to 0, and so on.


  • 0
    J

    The test case has covered all negative numbers situation:

    Input: [-1]

    Output: 0

    Expected: -1

    I think it assumes that the subarray can't be empty.


  • 0
    Y

    but in this way, if the input is [-1], the sum will be refreshed to 0.


  • 0
    R

    I think you can use two counter variables, one for accumulating sum and one for largest value comparison. Initialize the comparison counter with the first value in the list. Return the comparison counter as the final result. Something like:

    int comparison = list[0] --> set to sum if sum > comparison in the loop

    int sum = 0 --> reset to 0 if sum < 0

    return comparison as the final result


  • 2
    M

    You need to check the max value when you go though the array once. if the max vale <= 0, you should return the max number in the array in case all the number <= 0.


  • 0
    E

    Here's my solution, no need for special check.

     int maxSubArray(int A[], int n) {
    
            int min = 0, max = std::numeric_limits<int>::min();
            int current = 0;
            int delta = std::numeric_limits<int>::min();
            
            for(size_t i = 0; i < n; ++i)
            {
                current += A[i];
                if(current > max)
                {
                    max = current;
                    if(max - min > delta)
                    {
                        delta = max - min;
                    }
                }
                if(current <= min)
                {//takes care of the all negative and zero case 
                    max = current;
                    if(max - min > delta)
                        delta = max - min;
                    min = current;
                }
            }
            return delta;
        }

  • 0
    R

    The following algorithm is accepted. It add a flag to take care of the all negative case.

     class Solution {
        public:
            int maxSubArray(int A[], int n) {
                int sum = A[0];
                int subsum = 0;
                bool flag = true; //This is the flag to take care of the all negative case
                for (int i = 0; i < n; ++i)
                {
                    if (subsum < 0) subsum = A[i];
                    else subsum += A[i];
                    
                    if (true && sum < A[i]) sum = A[i];
                    if (A[i]>0) {
                        flag = false;
                        sum = max(sum,max(subsum,A[i]));
                    }
                }
                return sum;
            }
        };

  • 0
    L

    The problem should definitely make it clear that one can buy and sell the stock on the same day. So in the worst case, one would only have zero profit instead of negative profit.

    The assumption was not clear for me at first. My solution failed for the input {1, 2}, whose expected result is 0, instead of -1 that is given by my solution.


Log in to reply
 

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