Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

Note:

If n is the length of array, assume the following constraints are satisfied:

* 1 ≤ n ≤ 1000

* 1 ≤ m ≤ min(50, n)

* Method 1: DP from top to bottom

* dp[m][j] means the result from nums[0] to nums[j] into m divisions.

* we have a index k, where 0 <= k < j.

* dp[m][j] = min(max(dp[m - 1][k], sum[j] - sum[k]))


```Java

class Solution {

private int[][] dp;

private int[] sum;

public int splitArray(int[] nums, int m) {

this.sum = new int[nums.length];

sum[0] = nums[0];

for(int i = 1; i < nums.length; i++)

sum[i] = sum[i - 1] + nums[i];

dp = new int[m + 1][nums.length];

for(int[] d : dp) Arrays.fill(d, Integer.MAX_VALUE);

return dfs(m, nums.length - 1);

}

// Return the result from nums[0] to nums[j] divided into m parts.

private int dfs(int m, int j){

if(m == 1) return sum[j];

if(m > j + 1) return Integer.MAX_VALUE;

if(dp[m][j] != Integer.MAX_VALUE) return dp[m][j];

int res = Integer.MAX_VALUE;

for(int k = 0; k < j; k++){

res = Math.min(res, Math.max(sum[j] - sum[k], dfs(m - 1, k)));

}

return dp[m][j] = res;

}

}

```

* Method 2: from bottom to top

```Java

class Solution {

public int splitArray(int[] nums, int m) {

int[] sum = new int[nums.length];

sum[0] = nums[0];

for(int i = 1; i < nums.length; i++) sum[i] = sum[i - 1] + nums[i];

int[][] dp = new int[m + 1][nums.length];

for(int[] d: dp) Arrays.fill(d, Integer.MAX_VALUE);

for(int i = 0; i < nums.length; i++){

dp[1][i] = sum[i];

}

for(int i = 2; i <= m; i++){

for(int j = i - 1; j < nums.length; j++){

for(int k = 0; k < j; k++){

dp[i][j] = Math.min(dp[i][j], Math.max(dp[i - 1][k], sum[j] - sum[k]));

}

}

}

return dp[m][nums.length - 1];

}

}

```

* Method 2: Binary Search


```Java

class Solution {

public int splitArray(int[] nums, int m) {

long r = 0, l = 0;

for(int num : nums){

l = Math.max(l, num);

r += num;

}

r++;

while(l < r){

long mid = l + (r - l) / 2;

int count = 1, temp = 0;

for(int i = 0; i < nums.length; i++){

if(temp + nums[i] > mid){

count++;

temp = nums[i];

}else{

temp += nums[i];

}

}

if(count > m) l = mid + 1;

else r = mid;

}

return (int)l;

}

}

```

### Reference

1. [花花酱 LeetCode 410. Split Array Largest Sum](http://zxi.mytechroad.com/blog/dynamic-programming/leetcode-410-split-array-largest-sum/)

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

put(key, value) - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.

Follow up:

* Could you do both operations in O(1) time complexity?

* Method 1: HashMap + PriorityQueue Both get and put are O(NlgN)

* We create a class node, which saves the freq, tick, key and val.

* We have a hashMap to save the key and Node.

* We create a priorityQueue to to save the nodes, the comparator of the priorityQueue is

1. if freq is not same, compare the freq.

2. if freq is the same, we compare the tick.

```Java

class LFUCache {

private static final class Node{

int key, val;

Node pre, next;

int freq, tick;

public Node(int key, int val, int freq, int tick){

this.key = key;

this.val = val;

this.freq = freq;

this.tick = tick;

}

}

private Map<Integer, Node> map;

private PriorityQueue<Node> pq;

private int capacity;

private int size;

private int tick;

public LFUCache(int capacity) {

this.map = new HashMap<>();

this.capacity = capacity;

pq = new PriorityQueue<Node>((n1, n2)->{

return n1.freq == n2.freq ? n1.tick - n2.tick: n1.freq - n2.freq;

});

}

public int get(int key) {

if(!map.containsKey(key) || capacity == 0) return -1;

Node node = map.get(key);

pq.remove(node);

node.freq++;

node.tick = tick++;

pq.offer(node);

return node.val;

}

public void put(int key, int value) {

if(capacity == 0) return;

Node node = null;

if(map.containsKey(key)){

node = map.get(key);

node.val = value;

pq.remove(node);

map.remove(key);

size--;

}else{

node = new Node(key, value, 0, tick);

}

node.freq++;

node.tick = tick++;

map.put(key, node);

if(size < capacity){

pq.offer(node);

size++;

}else{

Node lfu = pq.poll();

map.remove(lfu.key);

pq.offer(node);

}

}

}

/**

```

* Method 2: Two hashMap + doubleLinkedList O(1)

```Java

class LFUCache {

private static final class Node{

int key, val, freq;

Node pre, next;

public Node(int key, int val){

this.key = key;

this.val = val;

this.freq = 1;

}

}

private static final class DLLList{

Node head, tail;

int size;

DLLList(){

head = new Node(0, 0);

tail = new Node(0, 0);

head.next = tail;

tail.pre = head;

}

void add(Node node){

head.next.pre = node;

node.next = head.next;

node.pre = head;

head.next = node;

size++;

}

void remove(Node node){

node.pre.next = node.next;

node.next.pre = node.pre;

size--;

}

Node removeLast(){

if(size > 0){

Node node = tail.pre;

remove(node);

return node;

}

return null;

}

}

private Map<Integer, Node> map;

private Map<Integer, DLLList> countMap;

private int size;

private int capacity;

private int min;

public LFUCache(int capacity) {

this.capacity = capacity;

this.map = new HashMap<>();

this.countMap = new HashMap<>();

}

public int get(int key) {

if(!map.containsKey(key) || size == 0) return -1;

Node node = map.get(key);

update(node);

return node.val;

}

public void put(int key, int value) {

if(capacity == 0) return;

Node node = null;

if(map.containsKey(key)){

node = map.get(key);

node.val = value;

update(node);

}else{

node = new Node(key, value);

map.put(key, node);

if(size == capacity){

DLLList lastList = countMap.get(min);

map.remove(lastList.removeLast().key);

size--;

}

size++;

min = 1;

DLLList newList = countMap.getOrDefault(node.freq, new DLLList());

newList.add(node);

countMap.put(node.freq, newList);

}

}

private void update(Node node){

DLLList oldList = countMap.get(node.freq);

oldList.remove(node);

if(node.freq == min && oldList.size == 0) min++;

node.freq++;

DLLList newList = countMap.getOrDefault(node.freq, new DLLList());

newList.add(node);

countMap.put(node.freq, newList);

}

}

/**

```

### Reference

1. [花花酱 LeetCode 460. LFU Cache](http://zxi.mytechroad.com/blog/hashtable/leetcode-460-lfu-cache/)