C# Linear time solution - also gets us the indices where the sub-array begins and ends

  • 0

    Many posts discus Kadane’s Algorithm, which basically relolves around resetting the "localSum" to 0 if it ever drops below 0. However is code below is a slightly different approach and it also lets us calculate the start and end indices of the elements that make up the sub-array in question

    public class Solution {
        public int MaxSubArray(int[] array) {
            // We need 2 variables, localSum and maxSum that are both initialized to the 1st element.
            int localSum = array[0];
            int maxSum = array[0];
            // all lines marked 'Optional' are to compute the startIndex and endIndex of the sub-array that contribute to the maximum sum
            int startIndex = 0; // Optional
            int endIndex = 0; // Optional
            int s = 0; // Optional --> we call this "start-pointer"
            for (int i = 1; i < array.Length; i++) {
                // go from 2nd element to the last element, try to see if adding the current element to localSum gets us a better localSum. If it does, go ahead and add the current element to localSum
                if (array[i] + localSum > array[i]) {
                    localSum += array[i];    
                else {
                    // if adding current element to localSum does not get us a better answer, we are better of ditching the existing value in localSum and having only current value in localSum
                    localSum = array[i];
                    s = i; // Optional --> because we ditch all elements before this one, we set the "start-pointer" to this index.
                if (localSum > maxSum) {
                    // when localSum out-grows max-sum, we have a new max-sum
                     maxSum = localSum;
                    startIndex = s; endIndex = i; // Optional --> start-index = "start-pointer", end-index = (this index)
            return maxSum;

Log in to reply

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