Max sum contiguous subarray

Question

Find the contiguous subarray within an array, A of length N which has the largest sum.

Input Format:

The first and the only argument contains an integer array, A.

Output Format:

Return an integer representing the maximum possible sum of the contiguous subarray.

Constraints:

1 <= N <= 1e6 -1000 <= A[i] <= 1000

For example:

Input 1: A = [1, 2, 3, 4, -10]

Output 1: 10

Explanation 1: The subarray [1, 2, 3, 4] has the maximum possible sum of 10.

Input 2: A = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Output 2: 6

Explanation 2: The subarray [4,-1,2,1] has the maximum possible sum of 6.

Can you please tell me why the following code does not work, and what is the error in the code :

public class Solution {

public int maxSubArray(final List<Integer> A) {

    ArrayList<Integer> al = new ArrayList<Integer>();
    int sum = 0;
    int max = A.get(0);
    int min = A.get(0);
    for(int i = 0;i < A.size();i++){

        sum += A.get(i);
        al.add(sum);
        if(sum > max) max = sum;

    }

    //to find the min till the index of max
    for(int i = 0; al.get(i) != max;i++) {
        if(al.get(i) < min) min = al.get(i);
    }



    if(min < 0)return max-min;
    else return max;
}



}

1) I think the result can be empty; I’m not sure you handle that. 2) check 10 -100 100 (I’m from phone, can’t run) — user2956272

Elmar Mammadov Elmar Mammadov · Accepted Answer · 2019-09-22T21:38:09

Honestly I did not get exactly what you are trying to do, but anyway leaving here code sample which is pretty popular and simple for this problem using Dynamic Programming approach. This also so called Kadane's algorithm

public static int name(List<Integer> numbers) {

    int maxSum = numbers.get(0);
    int tempMax = maxSum;

    for (int i = 1; i < numbers.size(); i++) {
        tempMax = Math.max(numbers.get(i), numbers.get(i) + tempMax);
        maxSum = Math.max(maxSum, tempMax);
    }

    return maxSum;
}

Max sum contiguous subarray

1 Answers