Rina Loves Shopping

DP Approach:

This problem can be solved using Dynamic Programming. Let’s define two terms:

$dp[i]$ $=$ the optimal sub-array sum up to index $i$ by keeping the value of index $i$ itself

$arr[ i ]$$=$ the value of the array at index $i$.

If we take an array index $i$ and calculate the maximum sub-array sum by keeping the value of index $i$, then we have only two options. We can either take only the value at position $i$, or we can add the value of position $i$ with the maximum sub-array sum up to index $i$. So, the answer for $dp[i]$ would be the maximum of $dp[i-1] + arr[i]$ and $arr[i]$. The solution of the entire problem would be the maximum of all the $dp[i]$ from index $0$ to $N-1$. The time complexity of the DP solution would be $O(N)$, where $N$ is the size of the array.