SDE - 1

Brute force : Time complexity : O(n*n)
-----------------------------------------
1. Consider all subarrays possible. if array has n elements then there are n*(n+1)/2 subarrays possible.
2. Maintain two variables running_sum and max_sum.
3. Run two nested loops. Outer loop will denote starting point of the subarray and inner loop denote end point of the subarray.
4. Outer loop starts from i = 0 to n and inner loop starts from j = i to n. 
5. for each step in outer loop initialize running_sum to zero
6. for each step in inner loop increment running_sum by the element in that index and update max_sum
7. at the end max_sum is the ans


Optimised approach(DP) : Time complexity : O(n), Space Complexity : O(n)
--------------------------------------------
Assumption : 
a. Size of the array : n
b. Array contains negetive elements as well

Steps:
1. Consider solving the problem using DP.
2. let's initialize a variable max_sum and 1d array dp of size n.
2. dp[i] denotes maximum subarray sum ending with ith index.
3. Iterate over n elements i.e i = 0 to n.
4. At each step, we have two option either I append ith element to subarray sum ending with i-1 index or don't
5. dp[i] = maximum of dp[i-1] + num[i] and num[i]
6. also update max sum at each step, max_sum = maximum of max_sum and dp[i] 
7. max_sum is the ans

Optimized approach(DP) : Time complexity: O(n)
-----------------------------------------------

Assumption : 
a. Size of the array : n
b. Array contains negetive elements as well
c. product never goes of out of limit 

Steps:
1. Consider solving the problem using DP.
2. let's two 1d array max_product and min_product of size n and a variable max_product.
2. max_product[i] denotes maximum subarray product ending with ith index.
2. min_product[i] denotes minimum subarray product ending with ith index.
3. Iterate over n elements i.e i = 0 to n.
4. At each step, to fill max_sum[i] we have 3 options to choose
a. append minimum product subarray ending with i-1th index with ith element
b. append maximum product subarray ending with i-1th index with ith element
c. don't append 
5. max_product[i] = maximum of (max_product[i-1] * num[i]), (min_product[i-1] * num[i]) and num[i]
6. Similarly do same for min_product
6. Also at each step update max_product with max_product[i]
7. max_product is the ans

Tip 1: Understand fundamentals.
Tip 2: Practice few low level design problems
Tip 3: Also prepare some puzzles (refer to geeksforgeeks for puzzles)