*****NEED THE CODE IN C*****

#include  #include  int maxSubArray(int a[], int length) { int bestValue=a[0]; for (int i=0; ibestValue) { bestValue=sumSubArray; } } } return bestValue; } int main() { int a[9]={-2,1,-3,4,-1,2,1,-5,4}; printf("Max subarray of first array = %d ", maxSubArray(a,9)); int b[12]={1,1,-3,4,-1,9,1,-5,4,2,-4,2}; printf("Max subarray of second array = %d ", maxSubArray(b,12)); } 

Problem 3. (1 pts) Consider the maximum subarray problem was an earlier quiz: The maximum subarray of an array is a subarray whose elements have the largest possible sum. The input to the problem is an integer array a[ ] with length 'length'. Attached is a C language program maxSubArray.c, which has a function maxSubArray(int a[ ], int length) that returns the sum of the maximum subarray. The function has time complexity (n2), where n is the length of the array. Rewrite the function so that it has time complexity O(n) and space complexity O(1). (Note that in an earlier quiz, we used divide-and-conquer to get a time complexity O(nlogn), so the solution to the current problem leads to an even faster algorithm.) Hint: Let sk= largest sum of all subarrays that end at k. Determine cases to calculate sk