leetcode

commit b8cd5fabf3ef2254280eef58a35fdcfe23271ee6
parent 7c560aefd7e6297696da49b1367787f444b500bf
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sat, 22 Nov 2025 20:21:59 -0700

1262. greatest sum divisible by three

Diffstat:
M
greatest_sum_div_three.c
 | 
59
+++++++++++++++--------------------------------------------
A
greatest_sum_div_three.py
 | 
30
++++++++++++++++++++++++++++++

2 files changed, 45 insertions(+), 44 deletions(-)
diff --git a/greatest_sum_div_three.c b/greatest_sum_div_three.c
@@ -1,58 +1,29 @@
 // 1262. Greatest Sum Divisible by Three
-#include <limits.h>
-#include <math.h>
-#include <stdio.h>
-#include <stdlib.h>
+#include "leetcode.h"
 
 /*
  * given an integer array 'nums', return the maximum possible sum of elements of
  * the array such that it is divisible by three
  */
 
-int maxSumDivThree(int *nums, int nums_size) {
-  int sum = 0, oneone = INT_MAX, onetwo = INT_MAX, twoone = INT_MAX,
-      twotwo = INT_MAX, rem = 0;
-  for (int i = 0; i < nums_size; i++) {
-    sum += nums[i];
-    rem += nums[i] % 3;
-    if (nums[i] % 3 == 1) {
-      if (nums[i] <= oneone) {
-        onetwo = oneone;
-        oneone = nums[i];
-      } else if (nums[i] < onetwo)
-        onetwo = nums[i];
-    } else if (nums[i] % 3 == 2) {
-      if (nums[i] <= twoone) {
-        twotwo = twoone;
-        twoone = nums[i];
-      } else if (nums[i] < twotwo)
-        twotwo = nums[i];
+int maxSumDivThree(int *nums, int numsSize) {
+  int dp[2][3] = {{0, 0, 0}, {0, INT_MIN, INT_MIN}};
+  for (int i = 0; i < numsSize; i++) {
+    const int x = nums[i], y = x % 3;
+    for (int j = 0; j < 3; j++) {
+      int prev = j - y;
+      prev += (-(prev < 0)) & 3;
+      const int take = x + dp[~i & 1][prev];
+      const int skip = dp[~i & 1][j];
+      dp[i & 1][j] = fmax(take, skip);
     }
   }
-  rem %= 3;
-  if (rem == 1) {
-    if (oneone != INT_MAX && twoone != INT_MAX && twotwo != INT_MAX)
-      return sum - fmin(oneone, twoone + twotwo);
-    else if (oneone != INT_MAX)
-      return sum - oneone;
-    else
-      return 0;
-  } else if (rem == 2) {
-    if (oneone != INT_MAX && onetwo != INT_MAX && twoone != INT_MAX)
-      return sum - fmin(oneone + onetwo, twoone);
-    else if (twoone != INT_MAX)
-      return sum - twoone;
-    else if (oneone != INT_MAX && onetwo != INT_MAX)
-      return sum - oneone - onetwo;
-    else
-      return 0;
-  } else
-    return sum;
+  return fmax(0, dp[~numsSize & 1][0]);
 }
 
 int main() {
   int n1[] = {3, 6, 5, 1, 8}, n2[] = {4}, n3[] = {1, 2, 3, 4, 4};
-  printf("%d\n", maxSumDivThree(n1, 5)); // expect: 18
-  printf("%d\n", maxSumDivThree(n2, 1)); // expect: 0
-  printf("%d\n", maxSumDivThree(n3, 5)); // expect: 12
+  printf("%d\n", maxSumDivThree(n1, ARRAY_SIZE(n1))); // expect: 18
+  printf("%d\n", maxSumDivThree(n2, ARRAY_SIZE(n2))); // expect: 0
+  printf("%d\n", maxSumDivThree(n3, ARRAY_SIZE(n3))); // expect: 12
 }
diff --git a/greatest_sum_div_three.py b/greatest_sum_div_three.py
@@ -0,0 +1,30 @@
+# 1262. Greatest Sum Divisible by Three
+
+"""
+given an integer array 'nums', return the maximum possible sum of elements of
+the array such that it is divisible by three
+"""
+
+
+class Solution(object):
+    def maxSumDivThree(self, nums):
+        """
+        :type nums: List[int]
+        :rtype: int
+        """
+        dp = [[0, 0, 0], [0, float("-inf"), float("-inf")]]
+        for i, j in enumerate(nums):
+            k = j % 3
+            for m in range(3):
+                prev = (3 + m - k) % 3
+                take = j + dp[(i + 1) & 1][prev]
+                skip = dp[(i + 1) & 1][m]
+                dp[i & 1][m] = max(take, skip)
+        return max(0, dp[(len(nums) - 1) & 1][0])
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.maxSumDivThree(nums=[3, 6, 5, 1, 8]))
+    print(obj.maxSumDivThree(nums=[4]))
+    print(obj.maxSumDivThree(nums=[1, 2, 3, 4, 4]))