121. Best Time to Buy and Sell Stock
easy
Say you have an array for which the ith
element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Example 1:
1  Input: [7, 1, 5, 3, 6, 4] 
max. difference = 61 = 5 (not 71 = 6, as selling price needs to be larger than buying price)
Example 2:
1  Input: [7, 6, 4, 3, 1] 
In this case, no transaction is done, i.e. max profit = 0.
1 

139. Word Break
hard
Given a nonempty string s and a dictionary wordDict containing a list of nonempty words, determine if s can be segmented into a spaceseparated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.
For example, given
s = "leetcode"
,
dict = ["leet", "code"]
.
Return true because "leetcode"
can be segmented as "leet code"
.
1  class Solution { 
140. Word Break II
hard
Given a nonempty string s and a dictionary wordDict containing a list of nonempty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.
Return all such possible sentences.
For example, given
s = "catsanddog"
,
dict = ["cat", "cats", "and", "sand", "dog"]
.
A solution is ["cats and dog", "cat sand dog"]
.
1  public List<String> wordBreak(String s, Set<String> wordDict) { 
152. Maximum Product Subarray
medium
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,2,4]
,
the contiguous subarray [2,3]
has the largest product = 6
.
1  class Solution { 
174. Dungeon Game
hard
The demons had captured the princess (P) and imprisoned her in the bottomright corner of a dungeon. The dungeon consists of M x N
rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the topleft room and must fight his way through the dungeon to rescue the princess.
The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.
Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0’s) or contain magic orbs that increase the knight’s health (positive integers).
In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.
Write a function to determine the knight’s minimum initial health so that he is able to rescue the princess.
For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT> RIGHT > DOWN > DOWN.
1  class Solution { 
