Maximum Subarray


  • 0
    S

    Hi my above code is accepted. I'm using two variables sum and maxSum. if my current variable is going to give the Sum greater than the summation of previous Sum + Curent variable then I'm updating that Sum to current variable, else adding the current value to the prevSum. if sum is greater than maxsum at any point of time im jst updating the maxSUm to sum. Suggest me if you have any other simpler or optimal solution than this.

    class Solution {
    public:
        int maxSubArray(int A[], int n) {
            int maxSum=-32000,sum=0,i=0;
            if(n==1){
                return A[n-1];
            }
            
            while(i<n){
                if(A[i]>(A[i]+sum))
                    sum= A[i];
                else
                    sum+=A[i];
                if(sum>maxSum)
                    maxSum=sum;
                    i++;
            }
            return maxSum;
    };

  • 0
    S

    Hi my above code is accepted. I'm using two variables sum and maxSum. if my current variable is going to give the Sum greater than the summation of previous Sum + Curent variable then I'm updating that Sum to current variable, else adding the current value to the prevSum. if sum is greater than maxsum at any point of time im jst updating the maxSUm to sum.
    Suggest me if you have any other simpler or optimal solution than this.


  • 0
    S

    Hi @sundeep2, glad to see you telling idea. Just move your comment in post, make it obvious to everyone else.


  • 2
    Z

    my answer in Java, almost the same thinking with your solution

    public int maxSubArray(int[] A) {
        int n = A.length;
    	int max = Integer.MIN_VALUE;
    	int sum = 0;
    	
    	for (int i = 0; i < n; i++) {
    		sum += A[i];
    		max = Math.max(max, sum);
    		if (sum < 0)
    			sum = 0;
    	}
    	return max;
    }

Log in to reply
 

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