0

I am trying to find a sub-array in array {-2, -3, 4, -1, -2, 1, 5, -3} where the sum of the values is the maximum and print this array out. The result should be [4, -1, -2, 1, 5]. But in my case the result is [-2, 1, 5], that is wrong 🤔

 static String maxSubArraySum(int[] a, int size)
{
    int max_so_far = a[0];
    int curr_max = a[0];

    for (int i = 1; i < size; i++)
    {
        curr_max = Math.max(a[i], curr_max+a[i]);
        max_so_far = Math.max(max_so_far, curr_max);
    }

    int [] res = Arrays.copyOfRange(a, curr_max, max_so_far);
    return Arrays.toString(res);

}

public static void main(String[] args)
{
    int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};
    int n = a.length;
    String arr = maxSubArraySum(a, n);
    System.out.println("Result is " + arr);
}

1 Answer 1

1

You need the indices to specify the range, not the real values of the array.
Also, copyOfRange range is from first element to last+1

You could do this:

import java.util.Arrays;

public class lol{

    static String maxSubArraySum(int[] a, int size)
    {
        int max_so_far = a[0];
        int curr_max = a[0];
        int curr_max_idx = 0;
        int max_so_far_idx = 0;
        for (int i = 1; i < size; i++)
        {
            curr_max = Math.max(a[i], curr_max+a[i]);
            if(curr_max==a[i]){
                curr_max_idx = i;
            }
            max_so_far = Math.max(max_so_far, curr_max);
            // i+1 to end at last + 1
            if(max_so_far==curr_max){
                max_so_far_idx = i + 1;
            }
        }
        int [] res = Arrays.copyOfRange(a, curr_max_idx, max_so_far_idx);
        return Arrays.toString(res);
    
    }
    
    public static void main(String[] args)
    {
        int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};
        int n = a.length;
        String arr = maxSubArraySum(a, n);
        System.out.println("Result is " + arr);
    }
}

or instead of Math.max() function, just use if statements and update curr_max and its index curr_max_idx

Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.