Advanced DSA
Advanced DSA - Arrays1 Max Sum Contiguous Subarray : Given array of size N, find the max sum of any contiguous chunk of elements.(Max sum of any subarray) Sol1: brute force : TC :O(N^3) Sol2 : Carry forward technique. TC :O(N^2) & SC : O(1) maxsum=Integer.MIN_VALUE; For(i=0;i<n;i++){ int sum=0; for (j=i;j<n;j++){ sum+=A[j]; maxsum=max(sum,maxsum); } } If we are iterating over all possible sub-arrays, it is not possible to reduce time complexity from O(N^2) as number of subarrays is N^2; Sol3: The answer will never have -ve numbers in corners Kidanes algorithm TC: O(N) SC: O(1) //reset sum when it goes -ve public int maxSubArray ( final List < Integer > A ) { int maxSum = Integer . MIN_VALUE ; int sum = 0 ; for ( int i = 0 ; i < A . size (); i ++){ sum += A . get ( i ); maxSum = Math . max...