当前位置: 代码迷 >> 综合 >> JAVA算法:求给定数组中连续子数组的最小和
  详细解决方案

JAVA算法:求给定数组中连续子数组的最小和

热度:45   发布时间:2024-01-15 19:17:50.0

JAVA算法:求给定数组中连续子数组的最小和

求给定数组中连续子数组的最小和。

package com.bean.algorithm.basic;public class SmallestSumContiguousSubarray {static int smallestSumSubarr(int arr[], int n) {int min_ending_here = 2147483647;// to store the minimum value encountered// so farint min_so_far = 2147483647;for (int i = 0; i < n; i++) {// if min_ending_here > 0, then it could// not possibly contribute to the// minimum sum furtherif (min_ending_here > 0)min_ending_here = arr[i];// else add the value arr[i] to// min_ending_hereelsemin_ending_here += arr[i];// update min_so_farmin_so_far = Math.min(min_so_far, min_ending_here);}return min_so_far;}public static void main(String[] args) {int arr[] = { 3, -4, 2, -3, -1, 7, -5 };int n = arr.length;System.out.print("Smallest sum: " + smallestSumSubarr(arr, n));}
}

程序运行结果:

Smallest sum: -6