Suppose you are given a one dimensional array of arbitrary integers. How will you find the maximum sum sub-array?
It can be solved using Kadane's algorithm. Iterate through the array from the beginning and compute the sum of the subarray ending at the current index. Compute the maximum of this current subarray sum and the value at current index. This maximum will be the current subarray sum. Compute the maximum of the current subarray sum and the maximum sum so far. Return the maximum in the last step once the whole array is iterated. Time complexity = \( O(n) \). public static int FindMaxSumSubArray(int[] array){ |