当前位置: 代码迷 >> 综合 >> JAVA算法:求最大连续上升(增加)子数组的和(详细求解)
  详细解决方案

JAVA算法:求最大连续上升(增加)子数组的和(详细求解)

热度:38   发布时间:2024-01-15 19:18:06.0

JAVA算法:求最大连续上升子数组的和(详细求解)

给定含有 n 个正的非重复整数的整型数组。

问题是找出满足条件为连续增加(上升)的子数组的最大和。

解释:什么是连续上升的子数组呢?就是子数组的元素按升序排列。


问题分析

 

伪代码如下:

Let arr be the array of size n
Let result be the required sumint largestSum(arr, n) result = INT_MIN  // Initialize resulti = 0while i < n// Find sum of longest increasing subarray// starting with icurr_sum = arr[i];while i+1 < n && arr[i] < arr[i+1]curr_sum += arr[i+1];i++; // If current sum is greater than current// result.if result < curr_sumresult = curr_sum; i++;
return result

算法设计

package com.bean.algorithm.basic;public class LargestSumContiguousIncreasingSubarray