时间戳

首页 > 解决方案 > 通过减少和征服找到最大的

java - 通过减少和征服找到最大的

问题描述

我有一个需要帮助解决的问题，基本上，这个问题要求我使用归约和征服算法来找到最大的元素。

问题描述：返回非空整数数组中的最大元素。我们将使用只考虑从给定索引开始并在另一个索引结束的数组的一部分的约定。通过这种方式，递归调用可以通过数组的任何部分进行。初始调用将传入索引 0 和最后一个元素的索引。

我想到的一些事情是使用递归来解决这个问题，但我一直在努力解决递归问题，因为它是一个我没有完全掌握的概念。任何人都可以指出我正确的方向吗？欢迎任何想法或建议。谢谢你。

到目前为止，这是我的想法：
编辑：更新的代码

public int max(int[] nums, int begin, int end) {

int maxVal = begin;

    if (begin == end) return nums[0];

    else if(begin < end){
      maxVal = max(nums, begin+1, end);
      if (maxVal > nums[end-begin]) return maxVal;
      else return nums[end-begin];
    }
    return maxVal;
  }

这将是输出：

最大值([2, 1, -2, 3, 8], 0, 4) → 8

最大值([6, 2, -4], 0, 2) → 6

最大值([3], 0, 0) → 3

标签： java

解决方案

执行以下操作：

public class Main {
    public static void main(String[] args) {
        // Tests
        System.out.println(max(new int[] { 2, 1, -2, 3, 8 }, 0, 4));
        System.out.println(max(new int[] { 2, 1, -2, 8, 3 }, 0, 4));
        System.out.println(max(new int[] { 2, 1, 8, -2, 3 }, 0, 4));
        System.out.println(max(new int[] { 2, 8, 1, -2, 3 }, 0, 4));
        System.out.println(max(new int[] { 8, 2, 1, -2, 3 }, 0, 4));
    }

    static int max(int[] nums, int begin, int end) {
        if (begin >= end) {
            return nums[end];
        }
        if (nums[begin] > nums[end]) {
            return max(nums, begin, end - 1);
        } else {
            return max(nums, begin + 1, end);
        }
    }
}

输出：

8
8
8
8
8

推荐阅读