Kadane's algorithm

Question: Largest sum continuous subarray

Given an array 'arr' of size 'n'. All we need to do is find a subarray that has the maximum sum.

Eg:- n = 6, arr = [-5, 4, 6, -3, 4, -1]. Output = 11, subarray = [4, 6, -3, 4]

For more detail on the question, you easily find it on google.

import java.util.Scanner;

public class LargestSumContinuousSubArray {
    /*
    In case all the elements are negative, as we discussed it will neglect the part.
    Thus, we set the max_sum to large negative value.
     */

    // Kadane's algorithm -> O(n)
    static int largestSum_Optimized(int[] arr, int size) {
        int max_sum = Integer.MIN_VALUE;
        int curr_sum = 0;

        for (int i = 0; i < size; i++) {
            curr_sum = curr_sum + arr[i];

            // finds maximum sum
            if (curr_sum > max_sum)
                max_sum = curr_sum;

            // found negative sum, thus resets the current sum to 0
            if (curr_sum < 0)
                curr_sum = 0;
        }

        return max_sum;
    }

    // Brute force approach - O(n^2)
    static int largestSum(int[] arr, int size) {
        int max_sum = -999;
        int sum = 0;

        for (int i = 0; i < size; i++) {
            sum = arr[i];
            for (int j = i + 1; j < size; j++) {
                sum = sum + arr[j];

                if (sum > max_sum)
                    max_sum = sum;
            }
        }
        return  max_sum;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int size = sc.nextInt();

        int[] arr = new int[size];
        for (int i = 0; i < size; i++)
            arr[i] = sc.nextInt();

        System.out.println(largestSum(arr, size));
    }
}

To reduce the time complexity to O(n), we use Kadane's algorithm.

Kadane's algorithm idea:-

1. Continuously add elements to find the subarray with the largest sum.

2. Stop when the sum becomes negative.

3. Neglect the part which gives a negative sum.

4. Repeat step 1 from the right part of the neglected part.

Examples with the above steps applied:-

Eg 1:- n = 6, arr = [-5, 4, 6, -3, 4, -1]

(-5, 4) -> -5 + 4 = 1

(4, 6) -> 4 + 6 = 10

(4, 6, -3) -> 4 + 6 -3 = 7

(4, 6, -3, 4) -> 4 + 6 -3 + 4 = 11

(4, 6, -3, 4, -1) -> 4 + 6 -3 + 4 -1 = 10

(6, -3) -> 6 -3 = 3

(6, -3, 4) -> 6 -3 + 4 = 7

(6, -3, 4, -1) -> 6 -3 + 4 -1 = 6

(-3, 4) -> -3 + 4 = 1

(-3, 4, -1) -> -3 + 4 -1 = 0

(4, -1) -> 4 -1 = 3

(-1) -> -1, neglected.

Eg 2:- n = 4, arr = [1, -2, 3, 2]

(1, -2) -> 1 -2 = -1, neglected.

(3, 2) -> 3 + 2 = 5

(2) -> 2, neglected.