Google Intern interview questions

Question: Given an array of integers, write a function that finds the contiguous subarray with the largest sum and returns the sum. This question is an example of a classic programming problem known as the Maximum Subarray problem. The solution to this problem requires the use of dynamic programming and can be approached in multiple ways, such as using the Kadane's algorithm or a divide-and-conquer approach.

Two dynamic programming questions. One is easy, the other is hard.