---
# System prepended metadata

title: 1262. Greatest Sum Divisible by Three
tags: [Leetcode, Dynamic Programming, Medium]

---

# 1262. Greatest Sum Divisible by Three
###### tags: `Leetcode` `Dynamic Programming` `Medium`
Link: https://leetcode.com/problems/greatest-sum-divisible-by-three/
## 思路
因为起始remainder是0 所以其他的都先设成Integer.MIN_VALUE
有三个状态 sum%3的余数分别是0，1，2
每一天(面对每一个数)都有两种选择 算进sum和不算进sum
## Code
```java=
class Solution {
    public int maxSumDivThree(int[] nums) {
        int[] remainder = new int[3];
        remainder[1] = Integer.MIN_VALUE;
        remainder[2] = Integer.MIN_VALUE;
        for(int num:nums){
            int[] temp = remainder.clone();
            for(int i=0; i<3; i++){
                remainder[i] = Math.max(temp[i], temp[(i-num%3+3)%3]+num);
            }
        }
        return remainder[0];
    }
}
```