_3196.java

packagecom.fishercoder.solutions.fourththousand;

publicclass_3196 {
publicstaticclassSolution1 {
/*
 * I knew it's a DP problem, I was close to figuring out the recurrence relationship.
 * <p>
 * Credit: https://leetcode.com/problems/maximize-total-cost-of-alternating-subarrays/solutions/5355138/dynamic-programming-and-space-optimized-beats-100-easy-to-understand/
 */
publiclongmaximumTotalCost(int[] nums) {
intlen = nums.length;
longadd = nums[0];
longsubtract = nums[0];
for (inti = 1; i < len; i++) {
longnewAdd = Math.max(add, subtract) + nums[i];
longnewSubtract = add - nums[i];

add = newAdd;
subtract = newSubtract;
 }
returnMath.max(add, subtract);
 }
 }
}