Maximum Number of Points with Cost LeetCode solution in Java

1
/*
2
   -> take a frame same width as points,this frame will contains most effective(which provide maximum sum)values which will later get
3
	added to next values from next row.
4

5
   -> conditions to update values in frame
6
		* we will keep only those values which will contribute maximum in next row addition
7

8
	e.g-->
9
		points --->[[1,2,3]
10
					[1,5,1]
11
					[3,1,1]]
12

13
		for 1st iteration frame <--- [1,2,3] rest of two loops will not affect frame so in
14
		2nd itreration frame <--------[2,7,4] <-------- [1,2,3] + [1,5,1]
15
		now we have to update frame so it can give max values for next row addition
16
		 0 1 2
17
		[2,7,4]
18
		  \
19
		[2,7,4]  check left to right--> just check value at index 0 can contribute more than curr_sum at index 1 but to do so it has to give up (1-0) a penalty,here 7 can contribute more than 2-1=1 in next sum.
20
		2 7 4        now check for index 2,where (7-1)>4
21
		   \
22
		2 7 6
23
					now do in reverse,can 6 contribute more than 7 no ( 7 >(6-1) )
24
					can 7 contibute more than 2 yes (2<(7-1)),so now  frame will be
25
		6 7 6       now we can cal optimal-frame for rest of the matrix.
26
	+   3 1 1
27
 -------------------
28
		9 8 7  check left to right--> can 9 can contibute 8>(9-1) no; can 8 can contibute for index 2 no simlier for right to left
29
*/
30

31
class Solution {
32
  public long maxPoints(int[][] points) {
33
    long[] frame = new long[points[0].length];
34

35
    for (int i = 0; i < points.length; i++) {
36
      for (int j = 0; j < frame.length; j++) frame[j] += points[i][j];
37

38
      for (int j = 1; j < frame.length; j++) frame[j] = Math.max(frame[j], frame[j - 1] - 1);
39

40
      for (int j = frame.length - 2; j >= 0; j--) frame[j] = Math.max(frame[j], frame[j + 1] - 1);
41

42
      for (long k : frame) System.out.println(k);
43
    }
44

45
    long ans = 0;
46
    for (int i = 0; i < frame.length; i++) {
47
      ans = Math.max(ans, frame[i]);
48
    }
49
    return ans;
50
  }
51
}