Skip to content

1746. Maximum Subarray Sum After One Operation 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
 public:
  int maxSumAfterOperation(vector<int>& nums) {
    int ans = INT_MIN;
    int regular = 0;
    int squared = 0;

    for (const int num : nums) {
      squared = max({num * num, regular + num * num, squared + num});
      regular = max(num, regular + num);
      ans = max(ans, squared);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
  public int maxSumAfterOperation(int[] nums) {
    int ans = Integer.MIN_VALUE;
    int regular = 0;
    int squared = 0;

    for (final int num : nums) {
      squared = Math.max(num * num, Math.max(regular + num * num, squared + num));
      regular = Math.max(num, regular + num);
      ans = Math.max(ans, squared);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def maxSumAfterOperation(self, nums: List[int]) -> int:
    ans = -math.inf
    regular = 0
    squared = 0

    for num in nums:
      squared = max(num**2, regular + num**2, squared + num)
      regular = max(num, regular + num)
      ans = max(ans, squared)

    return ans