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

• 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;
}
}
``````

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