FilesExpand file tree

 master

/

Problem312.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

39 lines (30 loc) · 1023 Bytes

 master

/

Problem312.java

Top

File metadata and controls

• Code
• Blame

39 lines (30 loc) · 1023 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

import java.util.List;

import java.util.ArrayList;

class Problem312 {

public static void main(String[] args) {

int[] nums = {3,1,5,8};

System.out.println(new Problem312().maxCoins(nums));

}

public int maxCoins(int[] nums) {

List<Integer> list = new ArrayList<>();

list.add(1);

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

list.add(nums[i]);

}

list.add(1);

int[][] dp = new int[list.size()][list.size()];

int sum = helper(list, 1, nums.length, dp);

return sum;

}

int helper(List<Integer> list, int left, int right, int[][] dp) {

if (left > right) return 0;

if (dp[left][right] > 0) return dp[left][right];

for (int i = left; i <= right; i++) {

int l = helper(list, left, i-1, dp);

int r = helper(list, i+1, right, dp);

int val = list.get(i) * list.get(left-1) * list.get(right+1);

dp[left][right] = Math.max(dp[left][right], val + l + r);

}

return dp[left][right];

}

}