How to determine the length of the longest increasing contiguous sub-arrays in a given unsorted array?
since you are finding sub-array which is contiguous, you can apply this.
suppose array is 1 2 1 3 4 3 6
Consider any element, if it is part of increasing subarray, it must be larger than or equal to its previous element.
for 1, no previous element is present, so a subarray ending at 1 will have length 1
for 2, previous element is 1, so 2 is larger. So subarray ending at 2 will have sub-array ending at 1 plus one more element (present 2)
so simple dp approach is
dp[0] = 1 //single element subarray
for(int i = 1; i < n; i++)
if(arr[i] >= arr[i-1])
dp[i] = dp[i-1] + 1;
else
dp[i] = 1
maximum among the dp array is the length of the largest contiguous subarray
1 Like
Can we use Kadane’s algo here as well?