Google Interview Question — LeetCode 1423

In this post, we are going to discuss the leetcode problem no. 1423— Maximum Points You Can Obtain from Cards, which is recently asked in Google interviews.

Problem Analysis

This question is to find the maximum sum we can get by picking k numbers either from the head or the tail.

My Thinking Process

For this type of question, usually the first thing I do is, try to find out all the possibilities of numbers we can pick. So the possibilities are below:

1. Pick all the firstk numbers from the head
2. Pick all the first k-1 numbers from the head, and 1 number from the tail
3. Pick all the first k-2 numbers from the head, and 2 numbers from the tail
4. …
5. Pick 0 numbers from the head, and k numbers from the tail
6. Find the maximum sum from the above possibilities

Give the above analysis, the approach now becomes clearer:

1. we can start with the first possibility, find the sum current_sum of the first k numbers from the head
2. Remove the k^th number from the head (we can easily do this by using a stack), and add the last number from the tail, and update the current_sum