Introdução ao Subarray Máximo
O problema do Subarray Máximo nos pede para encontrar o subarray com a maior soma de um dado array. Este problema pode ser resolvido usando programação dinâmica e, mais especificamente, o Algoritmo de Kadane.
Problema de Submatriz Máxima
Dado um array de inteiros nums, encontre o subarray com a maior soma e retorne sua soma.
1 public class Solution {
2 public int maxSubArray(int[] nums) {
3 int maxSum = nums[0];
4 int currentSum = nums[0];
5
6 for (int i = 1; i < nums.length; i++) {
7 currentSum = Math.max(nums[i], currentSum + nums[i]);
8 maxSum = Math.max(maxSum, currentSum);
9 }
10
11 return maxSum;
12 }
13
14 public static void main(String[] args) {
15 Solution solution = new Solution();
16
17 int[] nums1 = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
18 int[] nums2 = {1};
19 int[] nums3 = {5, 4, -1, 7, 8};
20
21
22 System.out.println(solution.maxSubArray(nums1)); // Expected output: 6
23 System.out.println(solution.maxSubArray(nums2)); // Expected output: 1
24 System.out.println(solution.maxSubArray(nums3)); // Expected output: 23
25 }
26}Fonte: https://interviewing.io/questions/maximum-subarray