Поис максимального подмассива

Задача: Поиск максимального подмассива

Существует множество задач, в которых нам нужно найти максимальный смежный подмассив внутри некоторого массива(который имеет хотя бы один елемент), который имеет наибольшую суму.

К примеру, дан массив [−2,1,−3,4,−1,2,1,−5,4], смежный подмасив [4,−1,2,1] имеет наибольшую суму равную 6.

Решение даной задачи вы видете ниже. Производительность алгоритма равна Θ(n*lgn) Написано на Java.

Код:


import java.*;
import java.util.Arrays;
import java.lang.System;
import java.lang.Math;

class Triple {
	public int x;
	public int y;
	public double sum;
	
	public Triple(int x, int y, double sum) {
		this.x = x;
		this.y = y;
		this.sum = sum;
	}
}


public class DivConq {
	public static int majorityElement(int[] num) {
	    Arrays.sort(num);
	    return num[num.length / 2];
	}
	
	public static Triple findMaxCrossingSubarray(int[] array, int low, int mid, int high) {
		double left_sum = 0;
		int max_left = mid - 1;
		double sum = 0;
		for (int i = mid - 1; i >= low; i--) {
			if (i == mid - 1) {
				left_sum = array[i];
			}
			sum += array[i];
			if (sum >= left_sum) {
				left_sum = sum;
				max_left = i;
			}
 		}
		double right_sum = 0;
		int max_right = mid;
		sum = 0;
		for (int i = mid; i = right_sum) {
				right_sum = sum;
				max_right = i;
			}
		}
		System.out.println(max_left +" "+ max_right +" "+ (left_sum + right_sum));
		return new Triple(max_left, max_right, left_sum + right_sum);
	}
	
	public static Triple findMaxSubarray(int[] array, int low, int high) {
		Triple left, right, cross;
		if (low == high) {
			return new Triple(low, high, array[low]);
		} else {
			int mid = (int)Math.floor((low + high + 1)/2);
			left = findMaxSubarray(array, low, mid - 1);
			right = findMaxSubarray(array, mid, high);
			cross = findMaxCrossingSubarray(array, low, mid, high);
			if (left.sum > right.sum && left.sum > cross.sum) {
				return left;
			} else if (right.sum > left.sum && right.sum > cross.sum) {
				return right;
			} else {
				return cross;
			}
		}
	}
	
	public static void main(String args[]) {
//		int[] array = {-9, 4, 1, 2, -1, -14, -3, 4};
		int[] array = {9, -3, -25, 20, -3, -16, -23, 18, 20, -20, -7, 12, -5, -22, 15, -4, 7, 23};
		Triple result = findMaxSubarray(array, 0, array.length - 1);
		
		System.out.println("SUM:" + (int)result.sum);
		System.out.println("X:" + (int)result.x +" "+ "Y:" + (int)result.y);
		for (int i = result.x; i <= result.y; i++) {
			System.out.print(array[i]+" ");
		}
	}
}

Краткое описание:

Так как мы используем подход "разделяй и властвуй", то из названия понятно, что мы будем разделять массив на меншие, тоесть использовать рекурсию. Так как наш подмассив при расбиении может быть как в левой части массива, так и в правой и быть частью левой и правой части, то мы вызиваем дважди функцию findMaxSubarray(для левой части и для правой), и один раз функцию findMaxCrossingSubarray, которая ищет максимальный подмассив, кторый может лежать и в левой части и в правой одновременно.

Как по мне код понятный. Если понадобится более подробное обьяснение алгоритма, то я обязательно напишу его, а пока извените пишу чисто для себя. Буду использовать как шпаргалку. Всем спасибо!!!

LikeMe: