You are given an array arr={1, -2,3,4,5,6}. What is the output of the following pseudocode?void fun(int arr[],int n){ int dp[n] for(int i=0;i<n;i++)dp[i]=0 dp[0]=arr[0] int ans=max(0,arr[0]); for(int i=1;i<n;i++){ dp[i]=Max(dp[i-1]+arr[i],arr[i]) ans=max(ans,dp[i]) } print(ans);}fun(arr,6) output is ?

The pseudocode provided is a dynamic programming solution for finding the maximum subarray sum in an array. The function fun takes an array arr and its size n as input.

Here's a step-by-step explanation of the pseudocode:

1. An array dp of size n is initialized with all elements as 0. This array will store the maximum subarray sum ending at each index of the array arr.

2. The first element of dp is set to the first element of arr, and ans is initialized as the maximum of 0 and the first element of arr. This is because the maximum subarray sum ending at the first index is the first element itself.

3. Then, for each element in arr from the second element to the last, the maximum subarray sum ending at that index is calculated as the maximum of the sum of the maximum subarray sum ending at the previous index and the current element, and the current element itself. This is stored in dp[i].

4. ans is updated as the maximum of ans and dp[i] for each i.

5. Finally, ans is printed, which is the maximum subarray sum in arr.

Now, let's calculate the output for the given array arr={1, -2,3,4,5,6}:

• For i=0, dp[0]=arr[0]=1 and ans=1.
• For i=1, dp[1]=Max(dp[0]+arr[1],arr[1])=Max(1-2,-2)=-1 and ans=Max(ans,dp[1])=Max(1,-1)=1.
• For i=2, dp[2]=Max(dp[1]+arr[2],arr[2])=Max(-1+3,3)=3 and ans=Max(ans,dp[2])=Max(1,3)=3.
• For i=3, dp[3]=Max(dp[2]+arr[3],arr[3])=Max(3+4,4)=7 and ans=Max(ans,dp[3])=Max(3,7)=7.
• For i=4, dp[4]=Max(dp[3]+arr[4],arr[4])=Max(7+5,5)=12 and ans=Max(ans,dp[4])=Max(7,12)=12.
• For i=5, dp[5]=Max(dp[4]+arr[5],arr[5])=Max(12+6,6)=18 and ans=Max(ans,dp[5])=Max(12,18)=18.

So, the output of fun(arr,6) is 18.