Find the subarray with the max sum

In an interview I was asked to solve the following problem:


find a subarray with max sum

I have written a piece of code for the same. I need your help in reviewing this code.

package com.ankit.rnd;

public class MaxSubArrSum {

    int largestSum=0;
    int previousLargestSum=0;

    public static void main(String[] args) {
        // int [] array = {-2,1,-3,4,-1,2,1,-5,4};
        int [] array = {-5,1,-3,7,-1,2,1,-4,6};
        // int [] array = {-2,-3,-4,2};

        MaxSubArrSum obj = new MaxSubArrSum();

        for(int varindex=0;varindexlargestSum){
                previousLargestSum=largestSum;
                largestSum=sum;
                for(int k=0;k<currentArray.length;k++){
                    System.out.print(currentArray[k] + "|");

                }
                System.out.println("");
            }
        }
        return largestSum;
    }

    private int calculate(int [] currentArr){
        int sumOfElements =0;
        for(int index=0;index<currentArr.length;index++){
            sumOfElements +=currentArr[index];

        }
        //System.out.println("sum is:" + sumOfElements);
        return sumOfElements;
    }    
}

Reading and debugging your code and two other answers pops up. (And a third one popped up while writing this answer)

There's a whole lot to say about your code. I will provide comments about your existing code and also comment about a different way to think about the problem.

You have a whole lot of commented code, and you don't write why it has been commented. Either way, I would recommend removing all your commented code before putting it up for review.

The //needs a fix comments here almost made me close the question for not being working code. Your code works (even though it is inefficient) so remove all such commented code:

/*
                 * if(psuedoIndex == array.length){ //needs a fix. as we
                 * have reached the end of the array. //currentArray[j] =
                 * array[psuedoIndex-1]; currentArray[j] = 0; break; } else{

if(in ==0){
            tempArr[i] = arr[i];
        }
        else{
            tempArr[i-in] = arr[i];
        }

There is no need to treat in ==0 as a special case here. Your else can take care of that as well. Replace all this with:

tempArr[i-in] = arr[i];

currentArray = new int[i + 1];
            currentArray = new int[i+1];

Please use consistent spacing. And this applies to all your code. I recommend using spaces around + signs and such.

Compare

for (int j = 0; j <= i; j++) {

vs.

for(int i=0;i<array.length;i++){

I prefer the first version. No need to make code too compact. Itwillonlymakeithardertoread (right?).

if((sum = calculate(currentArray))>largestSum){

Sure, this works, but I think it would be more readable by splitting it on two lines.

int sum = calculate(currentArray);
if (sum > largestSum) {

private int calculate(int [] currentArr){

• Non-optimal spacing in both the method declaration and method body.

• Unclear method name. calculate what exactly? Rename it to calculateSum, please.

• Perfect use-case for a for-each loop.

-
Here's what I would do:

private int calculate(int[] currentArr) {
    int sumOfElements = 0;
    for (int value : currentArr) {
        sumOfElements += value;
    }
    return sumOfElements;
}

for(int k=0;k<currentArray.length;k++){
    System.out.print(currentArray[k] + "|");
}

There is a Arrays.toString method, use it.

System.out.print(Arrays.toString(currentArray));

A different approach

You're using way too many for-loops for my taste.

Consider your starting array:

int[] array = {-5,1,-3,7,-1,2,1,-4,6};

It starts with a negative number, and as you want to find the sub-array with the largest sum, there's no need to start counting on a negative number.

So, skipping that one we have these left:

int[] array = {1,-3,7,-1,2,1,-4,6};

By starting on \$1\$ and looping until you encounter a negative number, you can see that \$1 + -3 = -2\$, which makes this part unnecessary to check. It will not improve your array. The highest sum we can create out of this is simply \$1\$ for now.

Skipping the \$1\$ and \$-3\$ and we end up with:

int[] array = {7,-1,2,1,-4,6};

Now let's start looping. \$7 + -1 = 6\$ so that's good, let's continue.

\$2 + 1 + -4 = -1\$ OK, that ended up being a not so pleasant experience, but considering the \$6\$ we have from before, we end up with \$5\$ so let's continue.

\$6\$ now that's good. And now the array has ended. Adding this to our previous result and we end up with \$5 + 6 = 11\$ and we have our final result.

There's no need to start the original looping at 2 which will only count 2,1,-4,6 as the 7,-1 in the beginning of the array will give a more positive result than starting from this 2.

By taking this in consideration, you can increase the speed of your algorithm a lot.

The code for this approach can be found and review in my Code Review question

Edit: Another addition. You don't provide a method to retrieve the result without printing it. Your way of returning the result seems to be to simply print it to the console. That's not a good way. You should have provided a method like this: int[] maxSubArraySum(int[] array)

StackExchange Code Review Q#52249, answer score: 9