Array ( [0] => [1] => questions [2] => Strings [3] => Max-subarray-sum )
Given an array of integers consists of positive and negative numbers. You have to find subarray with maximum sum.
First line contains the size of the first array. Next line contains the m integers separated by the spaces.
Print maximun Subarray sum.
8 2 6 -4 -7 3 -2 10 -1
11
5 -4 6 2 -1 7
14
6 3 2 -7 -1 4 6
10
Login to see Discussion
Approach1: Brute Force
Step-i) Initialize a 2 dimensional matrix of size n*n array size.
Step-ii) Iterate a loop i from 0 to n.
Step-iii) Initialize a[i][i]=0.
Step-iv) Iterate other loop j from i+1 to n.
Step-v) Assign a[i][j] with sum of a[i-1][j] and a[j].
Step-vi) So now the sum’s of sub arrays are stored In the matrix.
Step-vii) Iterate through every element of the matrix and store the maximum value.
Step-viii) Return the maximum value.
Time complexity: O(n^2)
Space Complexity: O(n^2)
Note :
Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.
Login to see Solution